#include <bits/stdc++.h>
#define sz(X) (int)((X).size())
#define entire(X) X.begin(),X.end()
using namespace std; typedef long long ll;
void OJize(){cin.tie(NULL);ios_base::sync_with_stdio(false);}
template <class T1, class T2>ostream&operator<<(ostream &os,pair<T1,T2>const&x){os<<'('<<x.first<<", "<<x.second<<')';return os;}
template <class Ch, class Tr, class Container>basic_ostream<Ch,Tr>&operator<<(basic_ostream<Ch,Tr>&os,Container const&x){for(auto&y:x)os<<y<<" ";return os;}
typedef pair<ll,ll> pll;
// positive -> ccw; negative -> cw; 0 -> collinear
ll ccw(pll a, pll b, pll c){
auto [ax,ay] = a; auto [bx,by] = b; auto [cx,cy] = c;
return (bx-ax)*(cy-ay) - (by-ay)*(cx-ax);
}
struct disjointSet{
vector<int> par;
disjointSet(int n): par(n) {iota(entire(par), 0);}
void un(int x, int y){par[fd(x)] = fd(y);} // yr becomes parent
int fd(int x){return par[x]!=x? (par[x]=fd(par[x])) : x;}
};
typedef tuple<int,int,ll,ll> EDGE;
int n;
vector<EDGE> edges;
tuple<ll, ll, vector<pair<int,int>>>
mst(ll T, ll C){
sort(entire(edges), [&](const EDGE &e1, const EDGE &e2){
auto [a1,b1,t1,c1] = e1;
auto [a2,b2,t2,c2] = e2;
return T*t1 + C*c1 < T*t2 + C*c2;
});
ll ts = 0, cs = 0;
disjointSet DS(n+1);
vector<pair<int,int>> ans;
for(auto [a,b,t,c]: edges){
if(DS.fd(a) == DS.fd(b)) continue;
DS.un(a, b), ts+= t, cs+= c;
ans.push_back({a,b});
}
return {ts, cs, ans};
}
tuple<ll,ll,ll> hullsearch(pll l, pll r){
auto [lt,lc] = l; auto [rt,rc] = r;
tuple<ll,ll,ll> ltup = {lt*lc,lt,lc}, rtup = {rt*rc,rt,rc};
auto ans = min(ltup, rtup);
auto [mt,mc,_] = mst(lc-rc, rt-lt);
pll m = {mt,mc};
if(ccw(r, m, l) < 0){
ans = min(ans, hullsearch(l, m));
ans = min(ans, hullsearch(m, r));
}
return ans;
}
int main(){OJize();
int m; cin>>n>>m;
for(int i=0; i<m; i++){
int a,b,t,c; cin>>a>>b>>t>>c;
edges.push_back({a,b,t,c});
}
auto [x0,y0,_] = mst(1, 0);
auto [x1,y1,__] = mst(0, 1);
auto [tc,t,c] = hullsearch({x0,y0}, {x1,y1});
cout<<t<<' '<<c<<"\n";
auto [___,____,TREE] = mst(t, c);
for(auto [a,b]: TREE) cout<<a<<' '<<b<<'\n';
}
