#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<array<int,4>>v;
int pr[100001];
int sz[100001];
int n,m;
int find(int x){
if(x==pr[x])return x;
return pr[x] = find(pr[x]);
}
bool mergegroup(int a,int b){
a = find(a);
b = find(b);
if(a==b)return 0;
if(sz[a]<sz[b])swap(a,b);
pr[b] = a;
sz[a]+=sz[b];
return 1;
}
pair<int,int> solve(int x,int y){
vector<array<int,2>> lol;
for(int i = 0;i<v.size();i++){
lol.push_back({v[i][2]*x+v[i][3]*y,i});
}
sort(lol.begin(),lol.end());
for(int i = 1;i<=n;i++){
pr[i] = i;
sz[i] = 1;
}
long long a = 0 , b = 0;
for(auto i:lol){
if(mergegroup(v[i[1]][0],v[i[1]][1])){
a+=v[i[1]][2];
b+=v[i[1]][3];
}
}
return {a,b};
}
void print(int x,int y){
vector<array<int,2>> lol;
for(int i = 0;i<v.size();i++){
lol.push_back({v[i][2]*x+v[i][3]*y,i});
}
sort(lol.begin(),lol.end());
for(int i = 1;i<=n;i++){
pr[i] = i;
sz[i] = 1;
}
long long a = 0 , b = 0;
for(auto i:lol){
if(mergegroup(v[i[1]][0],v[i[1]][1])){
cout<<v[i[1]][0]-1<<" "<<v[i[1]][1]-1<<endl;
}
}
}
long long all = 1e18;
map<pair<int,int>,int> mp;
int nx = 0 , ny = 0;
bool ss = 0;
void rec(pair<int,int>a,pair<int,int> b){
mp[a] = 1;
mp[b] = 1;
if(ss==0){
if(all>a.first*a.second){
all = a.first*a.second;
nx = 1 , ny = 0;
}
if(all>b.first*b.second){
all = b.first*b.second;
nx = 0 , ny = 0;
}
}
ss = 1;
int Y = a.second-b.second;
int X = a.first-b.first;
int gc = __gcd(abs(X),abs(Y));
X/=gc;Y/=gc;
X = -X;
pair<int,int> lol = solve(X,Y);
if(lol.first*lol.second<all){
all = lol.first*lol.second;
nx = X;
ny = Y;
}
if(mp[lol])return ;
else {
rec(a,lol);
rec(lol,b);
}
}
signed main(){
cin>>n>>m;
for(int i = 0;i<m;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
a++;b++;
v.push_back({a,b,c,d});
}
rec(solve(1,0),solve(0,1));
cout<<solve(nx,ny).first<<" "<<solve(nx,ny).second<<endl;
print(nx,ny);
return 0;
}
