#include <bits/stdc++.h>
using namespace std;
long long t[210],u[10010],v[10010],ti[10010],mo[10010],n,m,vmax=2000000000000000000,st,sm,p1,p2;
long long sumt,summ;
struct muchii{long long u,v,val,valt,valm;}a[10010];
long long tata(long long n)
{
if(t[n]==n)return n;
return t[n]=tata(t[n]);
}
long long x,xx,y,yy;
bool comp(muchii a,muchii b)
{
if(a.val!=b.val)return a.val<b.val;
if(a.u!=b.u)return a.u<b.u;
if(a.v!=b.v)return a.v<b.v;
return a.valt<b.valt;
}
void calculeaza(long long v1,long long v2)
{
for(long long i=0;i<n;++i)
t[i]=i;
for(long long i=1;i<=m;++i)
a[i]={u[i],v[i],ti[i]*v1+mo[i]*v2,ti[i],mo[i]};
sumt=summ=0;
sort(a+1,a+m+1,comp);
for(long long i=1;i<=m;++i)
{
if(tata(a[i].u)!=tata(a[i].v))
{
t[t[a[i].u]]=t[a[i].v];
sumt+=a[i].valt;
summ+=a[i].valm;
}
}
}
void scrie(long long v1,long long v2)
{
for(long long i=0;i<n;++i)
t[i]=i;
for(long long i=1;i<=m;++i)
a[i]={u[i],v[i],ti[i]*v1+mo[i]*v2,ti[i],mo[i]};
sort(a+1,a+m+1,comp);
for(long long i=1;i<=m;++i)
{
if(tata(a[i].u)!=tata(a[i].v))
{
t[t[a[i].u]]=t[a[i].v];
cout<<a[i].u<<' '<<a[i].v<<'\n';
}
}
}
long long det(long long x,long long y,long long xx,long long yy,long long xxx,long long yyy)
{
return x*yy+xx*yyy+xxx*y-xx*y-xxx*yy-x*yyy;
}
unordered_set<long long>viz;
void imbunatatire(int x,int y,int xx,int yy)
{
if(viz.find(x*1000000000000000000+y*1000000000000+xx*1000000+yy)!=viz.end())
return;
viz.insert(x*1000000000000000000+y*1000000000000+xx*1000000+yy);
calculeaza(abs(xx-x),abs(yy-y));
if(sumt*summ<vmax)
{
st=sumt,sm=summ;
vmax=sumt*summ;
p1=abs(xx-x);
p2=abs(yy-y);
}
if(det(x,y,xx,yy,sumt,summ)==0)
return;
long long c1=sumt,c2=summ;
imbunatatire(x,y,c1,c2);
imbunatatire(xx,yy,c1,c2);
}
int main()
{
cin>>n>>m;
for(long long i=1;i<=m;++i)
cin>>u[i]>>v[i]>>ti[i]>>mo[i];
calculeaza(1,0);
if(sumt*summ<vmax)
{
st=sumt,sm=summ;
vmax=sumt*summ;
p1=1;
p2=0;
}
x=sumt;
y=summ;
calculeaza(0,1);
if(sumt*summ<vmax)
{
st=sumt,sm=summ;
vmax=sumt*summ;
p1=0;
p2=1;
}
xx=sumt;
yy=summ;
imbunatatire(x,y,xx,yy);
cout<<st<<' '<<sm<<'\n';
scrie(1,1);
return 0;
}
