//#pragma GCC optimize("Ofast")
//#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vv vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vvp vector<vector<pi>>
int n,m;
struct edge{
int a,b,t,c,idx;
};
vector<edge> edges;
vector<int> weight;
pi sol;
vector<int> mstsol;
vector<int> currmst;
vi par,sizes;
struct dsu{
int find(int i){
return par[i] == i ? i : par[i] = find(par[i]);
}
void uni(int a, int b){
a = find(a); b = find(b);
if(a == b) return;
if(sizes[a] < sizes[b]) swap(a,b);
sizes[a] += sizes[b];
par[b] = a;
}
dsu(int n){
iota(par.begin(), par.end(), 0);
sizes.assign(n,1);
}
};
pi solve(){
sort(edges.begin(), edges.end(), [&](const edge &a, const edge &b){
return weight[a.idx] < weight[b.idx];
});
dsu d(n);
int tcost = 0, ccost = 0;
currmst.clear();
for(int i = 0; i < m; i++){
edge &a = edges[i];
if(d.find(a.a) != d.find(a.b)){
tcost += a.t; ccost += a.c;
d.uni(a.a, a.b);
currmst.pb(a.idx);
}
}
return {tcost, ccost};
}
pi sub(pi a, pi b){
return {a.first - b.first, a.second - b.second};
}
bool sopra(pi a, pi b){
//cout << (ll)((ll)a.first * b.second - (ll)a.second * b.first) << "\n";
return ((ll)((ll)a.first * b.second - (ll)a.second * b.first) >= 0LL);
}
signed main()
{
//cin.tie(0); cin.sync_with_stdio(0);cout.tie(0); cout.sync_with_stdio(0);
//ofstream fout("output.txt");
cin>>n>>m;
edges.resize(m); weight.resize(m);
par.resize(n);
sizes.resize(n);
for(int i = 0; i < m; i++){
edge a;
cin>>a.a>>a.b>>a.t>>a.c;
a.idx = i;
edges[i] = a;
}
//soluzione ottimale per t
for(int i = 0; i < m; i++){
int idx = edges[i].idx;
weight[idx] = edges[i].t;
}
pi a = solve();
pi best = a;
mstsol = currmst;
//soluzione ottimale per c
for(int i = 0; i < m; i++){
int idx = edges[i].idx;
weight[idx] = edges[i].c;
}
pi b = solve();
//swap a e b se b best
//area triangolo negativa quindi minimizzo per la migliore
if((ll)best.first * best.second > (ll)b.first * b.second){
best = b;
mstsol = currmst;
}
stack<pair<pi,pi>> s; s.push({a,b});
while(!s.empty()){
//change wwight
a = s.top().first, b = s.top().second;
//cout << a.first << " " << a.second << " | " << b.first << " " << b.second << "\n";
s.pop();
for(int i = 0; i < m; i++){
int idx = edges[i].idx;
weight[idx] = edges[i].c * (b.first - a.first) - edges[i].t * (b.second - a.second);
}
//run mst
pi p = solve();
//sopra retta a-b, punto peggiore
//cout << p.first << " " << p.second << "\n";
if(sopra(sub(b,a),sub(p,a)) ){
//cout << "sburra\n";
continue;
}
if((ll)best.first * best.second > (ll)p.first * p.second){
best = p;
mstsol = currmst;
}
s.push({a,p});
s.push({p,b});
}
sort(edges.begin(), edges.end(), [&](const edge &a, const edge &b){
return a.idx < b.idx;
});
cout << best.first << " " << best.second << "\n";
for(int &a:mstsol){
cout << edges[a].a << " " << edges[a].b << "\n";
}
return 0;
}
