#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Nmax = 1e4 + 5;
int n, m, i, A, B, coef1, coef2, t[Nmax];
ll ans = LLONG_MAX;
struct edge
{
int x, y, c, d;
bool operator < (const edge &other) const
{
return c * A + d * B < other.c * A + other.d * B;
}
} a[Nmax];
struct point
{
int x, y;
bool operator == (const point &other)
{
return x == other.x && y == other.y;
}
};
inline ll parr(point A)
{
return (ll) A.x * A.y;
}
int boss(int x)
{
if(t[x] == x) return x;
return t[x] = boss(t[x]);
}
point apm(int _A, int _B)
{
A = _A, B = _B;
sort(a+1, a+m+1);
point ans = {0, 0};
int i;
for(i=0; i<n; ++i) t[i] = i;
for(i=1; i<=m; ++i)
if(boss(a[i].x) != boss(a[i].y))
{
ans.x += a[i].c;
ans.y += a[i].d;
t[t[a[i].x]] = t[a[i].y];
}
return ans;
}
void print_sol(int _A, int _B)
{
A = _A, B = _B;
sort(a+1, a+m+1);
point ans = {0, 0};
vector<point> v;
int i;
for(i=0; i<n; ++i) t[i] = i;
for(i=1; i<=m; ++i)
if(boss(a[i].x) != boss(a[i].y))
{
ans.x += a[i].c;
ans.y += a[i].d;
t[t[a[i].x]] = t[a[i].y];
v.push_back({a[i].x, a[i].y});
}
cout << ans.x << ' ' << ans.y << '\n';
for(auto e : v)
cout << e.x << ' ' << e.y << '\n';
}
void solve(point A, point B)
{
int p = A.y - B.y, q = B.x - A.x;
point C = apm(p, q);
if(C == A || C == B) return;
if(parr(C) < ans)
coef1 = p, coef2 = q, ans = parr(C);
solve(A, C);
solve(C, B);
}
int main()
{
// freopen("input", "r", stdin);
// freopen("output", "w", stdout);
cin.sync_with_stdio(false);
cin >> n >> m;
for(i=1; i<=m; ++i)
cin >> a[i].x >> a[i].y >> a[i].c >> a[i].d;
point A = apm(1, 0);
point B = apm(0, 1);
if(parr(A) < ans)
coef1 = 1, coef2 = 0, ans = parr(A);
if(parr(B) < ans)
coef1 = 0, coef2 = 1, ans = parr(B);
if(A == B);
else solve(A, B);
print_sol(coef1, coef2);
return 0;
}
