#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
const int maxn = 1e5;
int n,m;
struct edge
{
int u,v,t,c;
long long coef;
};
bool cmp(edge x, edge y)
{
return x.coef < y.coef;
}
vector<edge> edges;
long long dot(pair<long long, long long> x, pair<long long, long long> y)
{
return x.first * y.first + x.second * y.second;
}
long long cross(pair<long long, long long> x, pair<long long, long long> y)
{
return x.first * y.second - x.second * y.first;
}
long long area(pair<long long, long long> a, pair<long long, long long> b, pair<long long, long long> c)
{
return cross({b.first - a.first, b.second - a.second}, {c.first - b.first, c.second - b.second});
}
int dsu[maxn+5];
void reset()
{
for(int i = 0; i < n; i++)
dsu[i] = i;
}
int par(int u)
{
if(dsu[u] == u) return u;
return dsu[u] = par(dsu[u]);
}
bool unite(int u, int v)
{
u = par(u);
v = par(v);
if(u == v) return false;
dsu[v] = u;
return true;
}
vector<edge> print;
pair<long long, long long> f(pair<long long, long long> axis, bool yes)
{
for(auto &e: edges)
e.coef = dot(axis,{e.t,e.c});
sort(edges.begin(),edges.end(),cmp);
pair<long long, long long> ans = {0,0};
reset();
for(auto e: edges)
{
if(unite(e.u,e.v))
{
ans.first += e.t;
ans.second += e.c;
if(yes) print.push_back(e);
}
}
return ans;
}
vector<pair<long long, long long>> ans;
vector<pair<long long, long long>> trace;
void divide(pair<long long, long long> lp, pair<long long, long long> rp, pair<long long, long long> l, pair<long long, long long> r)
{
pair<long long, long long> axis = {lp.second - rp.second, rp.first - lp.first};
auto mp = f(axis,0);
// cout << mp.first << ' ' << mp.second << '\n';
if(area(lp,mp,rp) <= 0)
{
ans.push_back(lp);
trace.push_back(l);
ans.push_back(rp);
trace.push_back(r);
return;
}
divide(lp,mp,l,axis);
divide(mp,rp,axis,r);
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
edge e;
cin >> e.u >> e.v >> e.t >> e.c;
edges.push_back(e);
}
pair<int,int> x = {1,0};
pair<int,int> y = {0,1};
divide(f(x,0),f(y,0),x,y);
long long total = 1e18;
pair<long long, long long> opt;
pair<long long, long long> optax;
for(int i = 0; i < ans.size(); i++)
{
if(total > ans[i].first * ans[i].second)
{
total = ans[i].first * ans[i].second;
opt = ans[i];
optax = trace[i];
}
}
cout << opt.first << ' ' << opt.second << '\n';
f(optax,1);
for(auto e: print)
{
cout << e.u << ' ' << e.v << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
