//
// main.cpp
// IntensiveCamp 1 2025
//
// Created by Ali AlSalman on 24/01/2025.
//
#include <bits/stdc++.h>
template<typename T>
using vec = std::vector<T>;
using namespace std;
typedef vec<pair<int, int>> mst_t;
typedef pair<long long, long long> cost_time_t;
typedef pair<mst_t, cost_time_t> mst_res_t;
vec<function<bool(array<int, 4>, array<int, 4>)>> call_backs;
bool mask = true;
vec<bool> vs;
vec<vec<array<int, 3>>> adj;
mst_res_t mst(int piv, long long a = -1, long long b = -1, bool construct = false) {
mst_t tree;
long long sum_c = 0, sum_t = 0;
auto cmp_maker = [](int i, long long a = -1, long long b = -1) -> function<bool(array<long long, 4>, array<long long, 4>)>{
if (i == 1 || i == 2) {
return [i](array<long long, 4> lhs, array<long long, 4> rhs) -> bool {
return lhs[i + 1] > rhs[i + 1];
};
} else {
return [a, b](array<long long, 4> lhs, array<long long, 4> rhs) -> bool {
return a * lhs[2] + b * lhs[3] > a * rhs[2] + b * rhs[3];
};
}
};
priority_queue<
array<long long, 4>,
vec<array<long long, 4>>,
decltype(cmp_maker(piv, a, b))
> q(cmp_maker(piv, a, b)); q.push({0, -1, 0, 0});
while (!q.empty()) {
auto [u, v, _c, _t] = q.top(); q.pop();
if (vs[u] == mask) continue;
vs[u] = !vs[u]; if (construct && 0 <= u && 0 <= v) tree.push_back({u, v});
sum_c += _c; sum_t += _t;
for (auto [c, c_c, c_t] : adj[u]) if (vs[c] != mask) {
q.push({c, u, c_c, c_t});
}
}
mask = !mask;
return {tree, {sum_c, sum_t}};
}
typedef array<long long, 3> producer;
typedef pair<cost_time_t, producer> cnvx_t;
cnvx_t cnvx(cnvx_t a, cnvx_t b) {
auto min_p = [](cnvx_t a, cnvx_t b) {
if (a.first.first * a.first.second <= b.first.first * b.first.second) return a;
return b;
};
cnvx_t p = {
mst(3, a.first.second - a.first.first, b.first.first - b.first.second).second,
{ 3, a.first.second - a.first.first, b.first.first - b.first.second }
};
if (p == a || p == b) return min_p(a, b);
return min_p(cnvx(a, p), cnvx(b, p));
}
void solve() {
int n, m;
cin>>n>>m; vs.resize(n); adj.resize(n);
while (m--) {
int a, b, c, d;
cin>>a>>b>>c>>d;
adj[a].push_back({b, c, d});
adj[b].push_back({a, c, d});
}
auto c_point = mst(1).second;
auto t_point = mst(2).second;
auto opt = cnvx({
c_point, { 1, -1, -1 }
}, {
t_point, { 2, -1, -1 }
});
cout<<opt.first.first<<" "<<opt.first.second<<endl;
for (auto [u, v] : mst(opt.second[0], opt.second[1], opt.second[2], true).first) {
cout<<u<<" "<<v<<endl;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int t = 1;
// cin>>t;
while (t--) solve();
}
