#include <bits/stdc++.h>
//http://www.boi2011.ro/resurse/tasks/timeismoney-sol.pdf
//https://www.cnblogs.com/TenderRun/p/5700737.html
using namespace std;
typedef pair<long long, long long> pll;
struct Edge{
int x;
int y;
long long a;
long long b;
long long val(long long la, long long lb) const {
return la*a + lb*b;
}
};
int n,m;
vector<Edge> edges;
long long ans1 = 1000000LL;
long long ans2 = 1000000LL;
vector<Edge> ea;
//dsu
vector<int> parent;
int getpar(int v){
if(parent[v] == v) return v;
parent[v] = getpar(parent[v]);
return parent[v];
}
void join(int u, int v){
int pu = getpar(u);
int pv = getpar(v);
parent[pu] = pv;
}
pll solve(long long la,long long lb){
//cout << la << " " << lb << endl;
sort(edges.begin(),edges.end(),[&](const Edge& e1, const Edge& e2){return e1.val(la,lb) < e2.val(la,lb);});
vector<Edge> cur;
for(int k = 0; k < n; k++){
parent[k] = k;
}
long long a1 = 0LL;
long long a2 = 0LL;
for(int k = 0; k < m; k++){
if(getpar(edges[k].x) != getpar(edges[k].y)){
join(edges[k].x,edges[k].y);
cur.push_back(edges[k]);
a1 += edges[k].a;
a2 += edges[k].b;
}
}
long long curanswer = a1*a2;
if(curanswer < ans1*ans2){
ans1 = a1;
ans2 = a2;
ea = cur;
}
return make_pair(a1,a2);
}
//>0 is ccw, <0 is cw, 0 is on the line
long long cross_productz(pll a, pll b, pll c){
return (b.first-a.first) * (c.second-b.second) - (c.first-b.first) * (b.second-a.second);
}
void dothing(pll pl, pll pr){
auto mid = solve(pl.second-pr.second,pr.first-pl.first);
//skip if mid is on the line between pl and pr
if(cross_productz(pl,pr,mid) >= 0){
//should never be > 0, but could be =0
return;
}
dothing(pl,mid);
dothing(mid,pr);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
edges = vector<Edge>(m);
for(int k = 0; k < m; k++){
int x,y;
long long a,b;
cin >> x >> y >> a >> b;
edges[k] = {x,y,a,b};
}
parent = vector<int>(n);
auto p1 = solve(1LL,0LL);
auto p2 = solve(0LL,1LL);
dothing(p1,p2);
cout << ans1 << " " << ans2 << "\n";
for(int k = 0; k < n-1; k++){
cout << ea[k].x << " " << ea[k].y << "\n";
}
return 0;
}
