#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;
}
};
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ll n, m;
cin >> n >> m;
DSU t, t1, t2;
vector<pair<ll, ll>> ans, ans1, ans2;
vector<edge> edges, edges1, edges2;
for (int i = 0; i < m; i++) {
ll x, y, C, T;
cin >> x >> y >> T >> C;
edges.PB({x, y,T, C, T});
edges1.PB({x, y,T, C, C});
edges2.PB({x, y,T, C, C + T});
t.create(x);
t.create(y);
t1.create(x);
t1.create(y);
t2.create(x);
t2.create(y);
}
sort(edges.B, edges.E);
ll c = 0, tim = 0, v = 0, v1 = 0, v2 = 0, c1 = 0, tim1 = 0, c2 = 0, tim2 = 0;
for (edge e : edges) {
if (t.unite(e.a, e.b)) {
ans.PB({e.a, e.b});
c += e.c;
tim += e.t;
}
} v = tim * c;
for (edge e : edges1) {
if (t1.unite(e.a, e.b)) {
ans1.PB({e.a, e.b});
c1 += e.c;
tim1 += e.t;
}
} v1 = c1 * tim1;
for (edge e : edges2) {
if (t2.unite(e.a, e.b)) {
ans2.PB({e.a, e.b});
c2 += e.c;
tim2 += e.t;
}
} v2 = c2 * tim2;
if (v <= v2 && v <= v1) {
cout << tim << P << c << L;
for (auto [u, v] : ans) cout << u << P << v << L;
}
else if (v1 <= v2 && v1 <= v) {
cout << tim1 << P << c1 << L;
for (auto [u, v] : ans1) cout << u << P << v << L;
}
else if (v2 <= v1 && v2 <= v) {
cout << tim2 << P << c2 << L;
for (auto [u, v] : ans2) cout << u << P << v << L;
}
}
