/*
Hint: use ternary search
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;
const int mxn = 205;
const int mxm = 10005;
const db MAX = 1e5;
struct Edge {
ll a, b, t, c;
db k;
bool operator < (const Edge& oth) const {
return k < oth.k;
}
};
int n, m, par[mxn], sz[mxn];
vector<Edge> v;
int fd(int u) {
return par[u] = (par[u] == u ? u : fd(par[u]));
}
bool unn(int u, int v) {
u = fd(u);
v = fd(v);
if(u == v) return false;
if(sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
par[v] = u;
return true;
}
void init(ll x) {
iota(par, par + n, 0);
fill(sz, sz + n, 1);
for(auto& [a, b, t, c, k] : v)
k = c * x + t * (MAX - x);
sort(v.begin(), v.end());
}
ll solve(db mid) {
init(mid);
int solt = 0, solc = 0;
for(auto [a, b, t, c, k] : v) {
if(unn(a, b)) {
solt += t;
solc += c;
}
}
return 1LL * solt * solc;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
v.resize(m);
for(auto& [a, b, t, c, w] : v) cin >> a >> b >> t >> c;
db l = 0, r = MAX;
for(int ite = 0; ite < 70; ite++) {
db m1 = (2 * l + r) / 3;
db m2 = (l + 2 * r) / 3;
if(solve(m1) < solve(m2)) r = m2;
else l = m1;
}
init(l);
vector<pair<int, int>> ans;
int sumt = 0, sumc = 0;
for(auto [A, B, t, c, k] : v) {
if(unn(A, B)) {
sumt += t;
sumc += c;
ans.push_back({A, B});
}
}
cout << sumt << ' ' << sumc << '\n';
for(auto [a, b] : ans) cout << a << ' ' << b << '\n';
}
