//
// 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;
vec<bool> vs;
vec<vec<array<int, 3>>> adj;
pair<vec<pair<int, int>>, pair<long long, long long>> mst(int piv) {
vec<pair<int, int>> tree; fill(vs.begin(), vs.end(), 0);
long long sum_c = 0, sum_t = 0;
auto cmp_maker = [](int i) -> function<bool(array<int, 4>, array<int, 4>)>{
if (i == 4) {
return [](array<int, 4> lhs, array<int, 4> rhs) -> bool {
return ((long long) lhs[2] * lhs[3]) > ((long long) rhs[2] * rhs[3]);
};
} else if (i == 5) {
return [](array<int, 4> lhs, array<int, 4> rhs) -> bool {
return ((long long) lhs[2] * rhs[3]) > ((long long) lhs[3] * rhs[2]);
};
} else if (i == 6) {
return [](array<int, 4> lhs, array<int, 4> rhs) -> bool {
return ((long long) lhs[3] * rhs[2]) > ((long long) lhs[2] * rhs[3]);
};
}
return [i](array<int, 4> lhs, array<int, 4> rhs) -> bool {
return lhs[i] > rhs[i];
};
};
priority_queue<
array<int, 4>,
vec<array<int, 4>>,
decltype(cmp_maker(piv))
> q(cmp_maker(piv)); q.push({0, -1, 0, 0});
while (!q.empty()) {
auto [u, v, _c, _t] = q.top(); q.pop();
if (vs[u]) continue;
vs[u] = 1; if (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]) {
q.push({c, u, c_c, c_t});
}
}
return {tree, {sum_c, sum_t}};
}
void solve() {
int n, m;
cin>>n>>m; vs.resize(n); adj.resize(n);
if (m == n - 1) {
pair<int, int> arr[m];
int s = 0, t = 0;
while (m--) {
int a, b, c, d;
cin>>a>>b>>c>>d; s += c; t += d;
arr[m] = {b, a};
}
cout<<s<<" "<<t<<endl;
for (auto [a, b] : arr) cout<<a<<" "<<b<<endl;
exit(0);
}
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});
}
pair<vec<pair<int, int>>, pair<int, int>> ans[] = {
mst(2),
mst(3),
mst(4),
mst(5),
mst(6)
};
int a = 0;
for (int i = 1; i < 5; i++) {
if (ans[i].second.first * ans[i].second.second < ans[a].second.first * ans[a].second.second) {
a = i;
}
}
cout<<ans[a].second.first<<" "<<ans[a].second.second<<endl;
for (auto [u, v] : ans[a].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();
}
