#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct Edge {
ll a,b,t,c;
};
vector<Edge> edges;
vector<ll> rep, sajz;
vector<pair<ll, ll>> res;
ll inf = 1e9;
pair<ll, ll> best = {inf,inf};
ll Find(ll v) {
return (rep[v]==v ? v : rep[v] = Find(rep[v]));
}
bool Union(ll a, ll b) {
a=Find(a); b=Find(b);
if(a==b) return 0;
rep[a] = b;
return 1;
}
ll n, m;
pair<ll, ll> mst(ll a, ll b) {
rep.assign(n+1, 0);
sajz.assign(n+1, 1);
for(ll i=1; i<=n; ++i) rep[i] = i;
pair<ll, ll> wynik = {0,0};
sort(edges.begin(), edges.end(), [&](Edge x, Edge y){
return x.t*a + x.c*b < y.t*a + y.c*b;
});
vector<pair<ll, ll>> kraw;
for(auto[a,b,t,c] : edges) {
if(Union(a,b)) {
wynik.first += t;
wynik.second += c;
kraw.push_back({a,b});
}
}
if(wynik.first * wynik.second < best.first * best.second) {
best = wynik;
res = kraw;
}
return wynik;
}
void rek(ll t1, ll c1, ll t2, ll c2) {
ll a = c2 - c1;
ll b = t1 - t2;
ll c = a*t1 + b*c1;
auto[t3,c3] = mst(a,b);
if(t3*a + c3*b == c) return;
rek(t1,c1,t3,c3);
rek(t3,c3,t2,c2);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(ll i=0; i<m; ++i) {
Edge e;
cin >> e.a >> e.b >> e.t >> e.c;
edges.push_back(e);
}
auto[t1,c1] = mst(0,1);
auto[t2,c2] = mst(1,0);
rek(t1, c1, t2, c2);
cout << best.first << " " << best.second << "\n";
for(auto[a,b] : res) cout << a << " " << b << "\n";
return 0;
}
