#define taskname "timeismoney"
#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define ff first
#define ss second
using namespace std;
const int maxn = 1e4 + 10;
int n, m, x[maxn], y[maxn], t[maxn], c[maxn], id[maxn], p[maxn], w[maxn], mark[maxn];
iii anss;
inline int fp(int u) {return !p[u] ? u : p[u] = fp(p[u]);}
inline bool uni(int u, int v)
{
if ((u = fp(u)) == (v = fp(v))) return 0;
return p[v] = u, 1;
}
inline ii mst(int T, int C)
{
int g = __gcd(T, C);
T /= g, C /= g;
for (int i=1; i<=m; i++) w[i] = T * t[i] + C * c[i], id[i] = i, mark[i] = 0;
fill(p+1, p+n+1, 0);
sort(id+1, id+m+1, [](int x, int y){return w[x] < w[y];});
ii ans = {0, 0};
for (int i=1; i<=m; i++)
{
int _id = id[i];
if (uni(x[_id], y[_id])) ans.ff += t[_id], ans.ss += c[_id], mark[_id] = 1;
}
return ans;
}
void solve(ii x, ii y)
{
if (x == y) return;
ii mid = mst(x.ss - y.ss, y.ff - x.ff);
anss = min(anss, {mid.ff * mid.ss, {x.ss-y.ss, y.ff-x.ff}});
if (mid == x || mid == y) return;
solve(x, mid);
solve(mid, y);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin>>n>>m;
for (int i=1; i<=m; i++) cin>>x[i]>>y[i]>>t[i]>>c[i], x[i]++, y[i]++;
ii xx = mst(0, 1), yy = mst(1, 0);
anss = {xx.ff * xx.ss, {0, 1}};
anss = min(anss, {yy.ff * yy.ss, {1, 0}});
solve(xx, yy);
ii tmp = mst(anss.ss.ff, anss.ss.ss);
cout<<tmp.ff<<" "<<tmp.ss<<"\n";
for (int i=1; i<=m; i++) if (mark[i]) cout<<x[i]-1<<" "<<y[i]-1<<"\n";
}
/**
5 7
0 1 161 79
0 2 161 15
0 3 13 153
1 4 142 183
2 4 236 80
3 4 40 241
2 1 65 92
**/
