#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;
typedef long long ll;
typedef __uint128_t lll;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct Edge {
ll a, b, t, m;
};
int n;
vector<Edge> edges;
vector<ll> rep, sajz;
ll Find(ll v) {
return (rep[v] == v ? v : rep[v] = Find(rep[v]));
}
bool Union(ll a, ll b) {
a = Find(a);
b = Find(b);
if (a == b) return 0;
if (sajz[b] > sajz[a]) swap(a, b);
rep[b] = a;
sajz[a] += sajz[b];
return 1;
}
vector<Edge> res;
/* ---- MST ----
liczenia na lll
wynik wraca jako ll (do IO)
*/
pair<ll, ll> mst(ll wsp1, ll wsp2) {
res.clear();
for (ll i = 0; i < n; ++i) rep[i] = i, sajz[i] = 1;
lll czas = 0;
lll money = 0;
sort(edges.begin(), edges.end(), [&](const Edge& x, const Edge& y) {
lll v1 = (lll)wsp1 * x.t + (lll)wsp2 * x.m;
lll v2 = (lll)wsp1 * y.t + (lll)wsp2 * y.m;
return v1 < v2;
});
for (auto [a, b, t, m] : edges) {
if (Union(a, b)) {
czas += t;
money += m;
res.push_back({a, b, t, m});
}
}
return { (ll)czas, (ll)money };
}
/* iloczyn t*m może wyjść poza ll */
vector<pair<lll, pair<ll, ll>>> odp;
void rek(ll x1, ll y1, ll x2, ll y2) {
ll a = y2 - y1;
ll b = x1 - x2;
ll g = gcd(a, b);
a /= g;
b /= g;
auto [t, m] = mst(a, b);
odp.push_back({ (lll)t * m, {a, b} });
if ((t == x1 && m == y1) ||
(t == x2 && m == y2) ||
((lll)a * t + (lll)b * m == (lll)a * x1 + (lll)b * y1))
return;
rek(x1, y1, t, m);
rek(t, m, x2, y2);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll e;
cin >> n >> e;
for (ll i = 0; i < e; ++i) {
ll a, b, t, m;
cin >> a >> b >> t >> m;
edges.push_back({a, b, t, m});
}
rep.assign(n, 0);
sajz.assign(n, 0);
auto [t1, m1] = mst(0, 1);
auto [t2, m2] = mst(1, 0);
rek(t1, m1, t2, m2);
odp.push_back({ (lll)t1 * m1, {0, 1} });
odp.push_back({ (lll)t2 * m2, {1, 0} });
lll INF = (lll)4e18 * 4e18;
pair<lll, pair<ll, ll>> ans = {INF, {0, 0}};
for (auto &x : odp)
ans = min(ans, x);
auto [_, para] = ans;
auto [a, b] = para;
auto [t, m] = mst(a, b);
cout << t << " " << m << "\n";
for (auto [x, y, _, __] : res)
cout << x << " " << y << "\n";
return 0;
}
