#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=2e2+5, mx=1e4+5;
ll n, m, dsu[nx], u[mx], v[mx], t[mx], c[mx], res=1e18, rest, resc;
vector<pair<ll, ll>> ans;
int find(int x)
{
if (dsu[x]==x) return x;
return dsu[x]=find(dsu[x]);
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=m; i++) cin>>u[i]>>v[i]>>t[i]>>c[i];
for (int x=1; x<=15; x++)
{
for (int y=1; y<=15; y++)
{
for (int i=0;i <n;i ++) dsu[i]=i;
vector<tuple<int, int>> edg;
ans.clear();
ll smt=0, smc=0;
for (int i=1; i<=m; i++) edg.push_back({x*t[i]+y*c[i], i});
sort(edg.begin(), edg.end());
for (auto [_, idx]:edg)
{
if (find(u[idx])==find(v[idx])) continue;
ans.push_back({u[idx], v[idx]});
smt+=t[idx], smc+=c[idx];
dsu[find(u[idx])]=find(v[idx]);
}
if (smt*smc<res)
{
res=smt*smc;
rest=smt;
resc=smc;
}
}
}
cout<<rest<<' '<<resc<<'\n';
for (auto [i, j]:ans) cout<<i<<' '<<j<<'\n';
}
