#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> ii;
typedef pair<ii,ii> iiii;
vector<iiii> edges;
vector<ii> rate;
const int bl=50;
const int maxn=202;
int n,m;
int a,b;
// MST: kruskal ??
int pset[maxn];
int sz[maxn];
int cnt_set;
void init() {
for(int i=1 ; i<=n ; i++) {
pset[i]=i;
sz[i]=1;
}
cnt_set=n;
}
int find_set(int s) {
if(s==pset[s]) return s;
return pset[s]=find_set(pset[s]);
}
void union_set(int u, int v) {
if(sz[u]>sz[v]) swap(u,v);
pset[u]=v;
sz[v]+=sz[u];
}
pair<int,int> solve() {
init();
int sum_t=0;
int sum_c=0;
for(iiii tmp: edges) {
int u=tmp.fi.fi;
int v=tmp.fi.se;
int t=tmp.se.fi;
int c=tmp.se.se;
int fu=find_set(u);
int fv=find_set(v);
if(fu==fv) continue;
else {
union_set(fu,fv);
sum_t+=t;
sum_c+=c;
}
}
return ii(sum_t,sum_c);
}
signed main() {
for(int i=0 ; i<=bl ; i++) {
for(int j=0 ; j<=bl ; j++) {
if(i==0&&j==0) continue;
if(__gcd(i,j)==1) {
rate.push_back(ii(i,j));
}
}
}
cin>>n>>m;
for(int i=1 ; i<=m ; i++) {
int u,v,t,c;
cin>>u>>v>>t>>c;
u++; v++;
edges.push_back(iiii(ii(u,v),ii(t,c)));
}
int finale=INT_MAX;
int anst,ansc;
ii X=ii(0,0);
for(ii tmp: rate) {
a=tmp.fi;
b=tmp.se;
sort(edges.begin(),edges.end(),[](const iiii &x, const iiii &y){return x.se.fi*a+x.se.se*b<y.se.fi*a+y.se.se*b;});
ii res=solve();
if(res.fi*res.se<finale) {
finale=res.fi*res.se;
anst=res.fi;
ansc=res.se;
X=ii(a,b);
}
}
a=X.fi;
b=X.se;
cout<<anst<<' '<<ansc<<'\n';
sort(edges.begin(),edges.end(),[](const iiii &x, const iiii &y){return x.se.fi*a+x.se.se*b<y.se.fi*a+y.se.se*b;});
init();
for(iiii tmp: edges) {
int u=tmp.fi.fi;
int v=tmp.fi.se;
int t=tmp.se.fi;
int c=tmp.se.se;
int fu=find_set(u);
int fv=find_set(v);
if(fu==fv) continue;
else {
union_set(fu,fv);
cout<<u-1<<' '<<v-1<<'\n';
}
}
}
