//Challenge: Accepted
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define maxn 25005
using namespace std;
struct edge{
int to = 0, t = 0, c = 0;
edge(int x, int z, int w) {
to = x, t = z, c = w;
}
edge();
};
vector<edge> adj[maxn];
vector<pii> hull, slope, ed;
const int inf = 1<<30;
pii mst(int n, int A, int B, bool getans) {
pii ret = make_pair(0, 0);
int mind[n], from[n];
pii save[n];
bool found[n];
for (int i = 0;i < n;i++) mind[i] = inf, found[i] = false, from[i] = -1;
mind[0] = 0;
save[0] = make_pair(0, 0);
for (int cnt = 0;cnt < n;cnt++) {
int mi = inf, ind = 0;
for (int i = 0;i < n;i++) {
if (!found[i] && mind[i] < mi) {
mi = mind[i];
ind = i;
}
}
ret.ff += save[ind].ff, ret.ss += save[ind].ss;
if (getans && from[ind] != -1) ed.push_back(make_pair(ind, from[ind]));
found[ind] = true;
mind[ind] = 0;
for (edge ed:adj[ind]) {
int nv = A * ed.t + B * ed.c;
if (nv < mind[ed.to]) {
mind[ed.to] = nv;
from[ed.to] = ind;
save[ed.to] = make_pair(ed.t, ed.c);
}
}
}
return ret;
}
void solve(int n, pii lef, pii rig) {
//cout << lef.ff << " " << lef.ss << " " << rig.ff << " " << rig.ss << endl;
int xdif = rig.ff - lef.ff, ydif = lef.ss - rig.ss;
pii mid = mst(n, ydif, xdif, false);
if (mid != lef && mid != rig && ydif * mid.ff + xdif * mid.ss < ydif * lef.ff + xdif * lef.ss) {
slope.push_back(make_pair(ydif, xdif));
hull.push_back(mid);
solve(n, lef, mid);
solve(n, mid, rig);
}
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0;i < m;i++) {
int a, b, t, c;
cin >> a >> b >> t >> c;
adj[a].push_back(edge(b, t, c));
adj[b].push_back(edge(a, t, c));
}
pii lef = mst(n, 1, 0, false), rig = mst(n, 0, 1, false);
hull.push_back(lef), hull.push_back(rig);
slope.push_back(make_pair(1, 0)), slope.push_back(make_pair(0, 1));
solve(n, lef, rig);
int ans = inf;
pii out, sl;
for (int i = 0;i < hull.size();i++) {
if (hull[i].ff * hull[i].ss < ans) {
ans = hull[i].ff * hull[i].ss;
out = hull[i];
sl = slope[i];
}
}
cout << out.ff << " " << out.ss << "\n";
mst(n, sl.ff, sl.ss, true);
for (auto i:ed) cout << i.ff << " " << i.ss << "\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
*/
