#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef unsigned long long ull;
typedef vector<int> vi;
const int mxn = 200, mxm = 10000;
short par[mxn];
vector<array<short,4>> edges;
short get(short u){return (par[u]<0?u:par[u]=get(par[u]));}
int n,m;
int timeismoney = 2e9;
pii timexmoney = {1,0};
pii oracle(int a, int b){
sort(all(edges),[&](const array<short,4> &A, const array<short,4> &B){
return A[3]*a + A[2]*b < B[3]*a + B[2]*b;
});
fill(par,par+n,-1);
int time = 0, money = 0;
for(const auto &[u,v,t,c] : edges){
if(get(u)==get(v));
else par[get(v)] = get(u), time += t, money += c;
}
if(timeismoney > time*money){
timeismoney = time*money;
timexmoney = {time,money};
}
return {time,money};
}
void divide(const pii &l, const pii &r){
int a = l.first - r.first, b = r.second - l.second;
auto [x,y] = oracle(a,b);
if(x*b + y*a == b*l.first + a*l.second) return;
divide(l,{x,y});
divide({x,y},r);
}
void solve(){
cin >> n >> m;
edges.resize(m);
for(auto &[u,v,t,c] : edges)
cin >> u >> v >> t >> c;
auto l = oracle(1,0);
auto r = oracle(0,1);
divide(l,r);
fill(par,par+n,-1);
sort(all(edges),[&](const array<short,4> &A, const array<short,4> &B){
return A[3]*timexmoney.first + A[2]*timexmoney.second <
B[3]*timexmoney.first + B[2]*timexmoney.second;
});
cout << timexmoney.first << ' ' << timexmoney.second << '\n';
for(const auto &[u,v,t,c] : edges){
if(get(u)==get(v));
else par[get(v)] = get(u), cout << u << ' ' << v << '\n';
}
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int t = 1;
// cin >> t;
while(t--){solve();}
}
