#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
constexpr int N = 200;
constexpr int M = 10'000;
int rep[N+9];
vector<pair<pair<ll,ll>,pair<ll,ll>>> kraw;
int fint(int a){
if (rep[a]==a)return a;
return rep[a]=fint(rep[a]);
}
void onion(int a, int b){
a=fint(a);
b=fint(b);
rep[a]=b;
}
ll wa,wb;
bool comp(pair<pair<ll,ll>,pair<ll,ll>> a, pair<pair<ll,ll>,pair<ll,ll>> b){
ll aa,bb;
aa = a.second.first*wa + a.second.second*wb;
bb = b.second.first*wa + b.second.second*wb;
return aa<bb;
}
ll best=1e18;
vector<pair<pair<ll,ll>,pair<ll,ll>>> uzyte;
pair<ll,ll> bestt;
pair<ll,ll> wynik;
pair<ll,ll> mst(int n){
for (int x=0;x<n;x++)rep[x]=x;
sort(kraw.begin(),kraw.end(),comp);
pair<ll,ll> odp={0,0};
uzyte.clear();
for (auto x:kraw){
int u,v;
u =x.first.first; v=x.first.second;
if (fint(u)==fint(v))continue;
uzyte.push_back(x);
onion(u,v);
odp={odp.first+x.second.first,odp.second+x.second.second};
}
ll temp=odp.first*odp.second;
if (temp<best){
best=temp;
bestt={wa,wb};
}
wynik=odp;
return odp;
}
void split(int n, pair<ll,ll> l, pair<ll,ll> r){
wb=-(l.first-r.first);
wa=(l.second-r.second);
pair<ll,ll> nowy=mst(n);
if (nowy==l || nowy==r || (wa*nowy.first+wb*nowy.second)==(wa*l.first+wb*l.second))return;
split(n,l,nowy);
split(n,nowy,r);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,a,b,c,d;
cin >> n >> m;
for (int x=0;x<m;x++){
cin >> a >> b >> c >> d;
kraw.push_back({{a,b},{c,d}});
}
wa=0; wb=1;
pair<ll,ll> l=mst(n);
wa=1; wb=0;
pair<ll,ll> r=mst(n);
split(n,r,l);
wa=bestt.first; wb=bestt.second;
mst(n);
cout << wynik.first << ' ' << wynik.second<<'\n';
for (auto x:uzyte){
cout << x.first.first << ' ' << x.first.second << '\n';
}
return 0;
}
