#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
template<typename T>
using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e18);
const int MOD = 998244353;
const bool DEBUG = 0;
const int MAXN = 205;
const int MAXM = 10005;
struct DSU
{
struct Node{ int p, sz; };
int cc;
vector<Node> dsu;
DSU(int n){
dsu.resize(n); cc=n;
forn(i,0,n){ dsu[i]={i,1}; }
}
int rt(int u){ return (dsu[u].p==u) ? u : dsu[u].p=rt(dsu[u].p); }
bool sameset(int u, int v){ return rt(u)==rt(v); }
void merge(int u, int v)
{
u=rt(u); v=rt(v);
if(u==v) return;
if(dsu[u].sz<dsu[v].sz) swap(u,v);
dsu[u].sz+=dsu[v].sz;
dsu[v].p=dsu[u].p;
cc--;
}
};
struct Edge
{
int u,v;
ll x,y;
int id;
bool operator<(const Edge& e){ return x+y < e.x+e.y; }
};
int n,m;
vector<Edge> edges;
vector<ii> bestedges;
ii best={3e9,3e9};
ll besta,bestb;
ii solve(ll a, ll b, bool fin=false)
{
vector<Edge> ve;
for(Edge e: edges)
{
ve.pb({e.u, e.v, a*e.x, b*e.y, e.id});
}
sort(ve.begin(), ve.end());
DSU dsu(n);
ll sumx=0,sumy=0;
for(Edge e: ve)
{
if(dsu.cc==1) break;
int u=e.u, v=e.v;
if(dsu.sameset(u,v)) continue;
dsu.merge(u,v);
sumx+=edges[e.id].x;
sumy+=edges[e.id].y;
if(fin) bestedges.pb({u,v});
}
ii res=ii(sumx, sumy);
if(res.F*res.S < best.F*best.S)
{
best=res;
besta=a;
bestb=b;
}
return res;
}
bool good(ii a, ii b, ii c)
{
return (c.S-b.S)*(b.F-a.F)>(b.S-a.S)*(c.F-b.F);
}
void rec(ii a, ii b)
{
ii res=solve(a.S-b.S, b.F-a.F);
if(good(a,res,b))
{
rec(a,res);
rec(res,b);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>m;
forn(i,0,m)
{
int u,v,x,y; cin>>u>>v>>x>>y;
edges.pb(Edge{u,v,x,y,i});
}
ii minx=solve(1,0);
ii miny=solve(0,1);
rec(minx, miny);
solve(besta, bestb, true);
cout<<best.F<<" "<<best.S<<'\n';
for(auto e: bestedges) cout<<e.F<<" "<<e.S<<'\n';
return 0;
}
