#include <bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int> trinca;
typedef tuple<double,int,int,int,int> aresta;
typedef tuple<int,int,int,int> quadra;
const int MAXN = 210;
const double INF = 1e16;
const double EPS = 1e-6;
vector<trinca> grafo[MAXN];
int processado[MAXN],N,M,tem_que_exbir;
int matA[MAXN][MAXN],matB[MAXN][MAXN];
vector<quadra> pares;
int Prim(double alpha,int minimiza_b){
pares.clear();
priority_queue<aresta, vector<aresta>, greater<aresta> > pq;
int s1 = 0,s2 = 0;
for(int i = 0;i<N;i++){
processado[i] = 0;
}
pq.push({0.0,0,0,0,-1});
while(!pq.empty()){
aresta davez = pq.top();
pq.pop();
int c1 = get<1>(davez),c2 = get<2>(davez);
int v = get<3>(davez),p = get<4>(davez);
if(processado[v]) continue;
processado[v] = 1;
s1 += c1;
s2 += c2;
if(p != -1) pares.push_back({min(p,v),max(p,v),c1,c2});
for(trinca nxt : grafo[v]){
int u = get<0>(nxt),l1 = get<1>(nxt),l2 = get<2>(nxt);
if(minimiza_b) swap(l1,l2);
if(processado[u]) continue;
pq.push({alpha*l1 + (1.0 - alpha)*l2,l1,l2,u,v});
}
}
return s1*s2;
}
int checa(double alpha){
return min(Prim(alpha,0),Prim(1.0 - alpha,1));
}
int main(){
cin >> N >> M;
for(int i = 1;i<=M;i++){
int u,v,w1,w2;
cin >> u >> v >> w1 >> w2;
grafo[u].push_back({v,w1,w2});
grafo[v].push_back({u,w1,w2});
}
double ini = 0.0,fim = 1.0;
while(fim - ini > EPS){
double m1 = ini + (fim - ini)/3.0;
double m2 = fim - (fim - ini)/3.0;
if(checa(m1) < checa(m2)){
fim = m2 - EPS;
}
else{
ini = m1 + EPS;
}
}
if(Prim(ini,0) < Prim(1.0 - ini,1)){
Prim(ini,0);
int s1 = 0,s2 = 0;
sort(pares.begin(),pares.end());
for(quadra davez : pares){
s1 += get<2>(davez);
s2 += get<3>(davez);
}
printf("%d %d\n",s1,s2);
for(quadra davez : pares){
printf("%d %d\n",get<0>(davez),get<1>(davez));
}
}
else{
Prim(1.0 - ini,1);
int s1 = 0,s2 = 0;
sort(pares.begin(),pares.end());
for(quadra davez : pares){
s2 += get<2>(davez);
s1 += get<3>(davez);
}
printf("%d %d\n",s1,s2);
for(quadra davez : pares){
printf("%d %d\n",get<0>(davez),get<1>(davez));
}
}
return 0;
}
