#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
struct Dsu {
vll p, sz;
Dsu(ll n) : p(n), sz(n, 1) {
iota(p.begin(), p.end(), 0);
}
ll find(ll v) {
if (p[v] == v)
return v;
return p[v] = find(p[v]);
}
bool uni(ll a, ll b) {
ll x = find(a), y = find(b);
if (x == y)
return 0;
if (sz[x] < sz[y])
swap(x, y);
sz[x] += sz[y];
p[y] = x;
return 1;
}
};
int main() {
// if (!freopen("timeismoney.in", "r", stdin)) return 0;
// if (!freopen("timeismoney.out", "w", stdout)) return 0;
ll n, m;
cin >> n >> m;
vector<tuple<ll, ll, ll,ll> > vec, vec2;
for (ll i = 0; i < m; ++i) {
ll a, b, c, d;
cin >> a >> b >> c >> d;
vec.push_back({c, d, a, b});
}
sort(vec.begin(), vec.end());
ll v = 1e18, cc, tt;
vector<pair<ll, ll> > pairs, pairs2;
for (auto [c,d, a, b]: vec) {
Dsu dsu(n);
ll c_cnt = 0, t_cnt = 0, used = 0;
vec2.push_back({d, c, a, b});
sort(vec2.begin(), vec2.end());
for (auto [c,d,a,b]: vec2) {
if (dsu.uni(a, b)) {
used++;
c_cnt += c;
t_cnt += d;
pairs.push_back({a, b});
}
}
if ((used ==n-1) && (v > c_cnt * t_cnt)) {
v = c_cnt * t_cnt;
cc = c_cnt;
tt = t_cnt;
pairs2 = pairs;
}
pairs.clear();
}
cout << cc << " " << tt << "\n";
for (auto [a, b]: pairs2)
cout << a << " " << b << "\n";
}
