#include "bits/stdc++.h"
#define P ' '
#define L '\n'
#define F first
#define S size()
#define PB push_back
#define B begin()
#define E end()
#define SS second
#define PBB pop_back()
using ll = long long;
using namespace std;
struct edge {
ll a, b, t, c, weight;
bool operator< (edge x) const {
return weight < x.weight;
}
};
struct DSU{
ll parent[202];
void create(ll x) {
parent[x] = x;
}
ll find(ll x) {
if (x == parent[x]) return x;
return parent[x] = find(parent[x]);
}
bool unite(ll a, ll b) {
a = find(a);
b = find(b);
if (a != b) {
parent[b] = a;
return 1;
}
return 0;
}
};
struct check {
ll v = 1e9, t = 0, c = 0;
vector<pair<ll, ll>> ans;
bool operator< (check x) const {
return v < x.v;
}
};
check best;
vector<edge> edges;
check MST(ll a, ll b) {
DSU t;
for (edge e : edges) {
t.create(e.a);
t.create(e.b);
}
vector<edge> e;
e = edges;
for (edge &i : e) i.weight = (i.t * a) + (i.c * b);
sort(e.B, e.E);
check out;
for (edge i : e) {
if (t.unite(i.a, i.b)) {
out.c += i.c;
out.t += i.t;
out.ans.PB({i.a, i.b});
}
}
out.v = out.c * out.t;
return out;
}
check solve(ll c1, ll c2, ll t1 ,ll t2) {
ll a = c1 - c2, b = t2 - t1;
check mst = MST(a, b);
if ((mst.c == c2 && mst.t == t2) || (mst.t == t1 && mst.c == c1)) return mst;
return best = min(solve(c1, mst.c, t1, mst.t), solve(mst.c, c2, mst.t, t2));
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ll n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
ll x, y, C, T;
cin >> x >> y >> T >> C;
edges.PB({x, y,T, C, 0});
}
check btime = MST(1, 0);
check bcost = MST(0, 1);
best = min(btime, bcost);
solve(btime.c, bcost.c, btime.t, bcost.t);
cout << best.t << P << best.c << L;
for (auto i : best.ans) cout << i.F << P << i.SS << L;
}
