#ifndef Local
#pragma GCC optimize("O3,unroll-loops")
const int lim=1e5+100;
#else
const int lim=3e3+100;
#endif
#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define pb push_back
const int mod=1e9+7;
using pii=pair<int,int>;
struct edge{
int x,y,c1,c2;
inline edge(){}
inline edge(int x,int y,int c1,int c2)
:x(x),y(y),c1(c1),c2(c2){}
};
int parent[201];
inline void init(int n){
for(int i=0;i<n;i++)parent[i]=i;
}
inline int find(int i){
if(parent[i]==i)return i;
return parent[i]=find(parent[i]);
}
inline bool unite(int i,int j){
int x=find(i),y=find(j);
if(x^y){
parent[x]=y;
return 1;
}
return 0;
}
#define lll 51001
bitset<lll>dp=1;
inline void solve(){
int n,m;
cin>>n>>m;
edge v[m];
int cnt[256];
memset(cnt,0,sizeof(cnt));
for(int i=0;i<m;i++){
cin>>v[i].x>>v[i].y>>v[i].c1>>v[i].c2;
cnt[v[i].c1]++;
}
edge ans[n-1],cur[n-1];
int ansbest=1e13;
for(int i=1;i<256;i++){
for(int j=1;j<cnt[i];j<<=1){
dp|=dp<<(i*j);
cnt[i]-=j;
}
dp|=dp<<(i*cnt[i]);
}
for(int AA=n-1;AA<lll;AA++){
if(!dp[AA])continue;
int l=n-1,r=lll-1;
//cerr<<AA<<" AA\n";
while(l<=r){
int mid=(l+r)>>1;
//if(AA==279)cerr<<l<<" "<<mid<<" "<<r<<"\n";
#define cost(x) (x.c1*mid+x.c2*AA)
sort(v,v+m,[&](edge&x,edge&y) -> bool {
return x.c1*mid+x.c2*AA<y.c1*mid+y.c2*AA;
});
init(n);
int curi=0,A=0,B=0;
for(int i=0;i<m&&curi<n-1;i++){
if(unite(v[i].x,v[i].y)){
cur[curi++]=v[i];
A+=v[i].c1;
B+=v[i].c2;
if(AA<A){
l=mid+1;
goto fail;
}
}
}
/*
if(AA==279){
cerr<<A<<" "<<B<<" "<<A*B<<" "<<ansbest<<" result\n";
}
*/
if(A*B<ansbest){
for(int i=0;i<n-1;i++){
ans[i]=cur[i];
}
ansbest=A*B;
}
r=mid-1;
fail:;
}
}
int A=0,B=0;
for(int i=0;i<n-1;i++){
A+=ans[i].c1;
B+=ans[i].c2;
}
cout<<A<<" "<<B<<"\n";
for(int i=0;i<n-1;i++){
cout<<ans[i].x<<" "<<ans[i].y<<"\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
#ifdef Local
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#else
#endif
int t=1;
//cin>>t;
while (t--)
{
solve();
}
}
