/*
Problem: https://oj.uz/problem/view/balkan11_timeismoney
Solution: http://www.boi2011.ro/resurse/tasks/timeismoney-sol.pdf
*/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define D(a) cerr << #a << " = " << a << endl
#else
#define D(a) 8
#endif
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define dforsn(i,s,n) for(int i=int(n-1);i>=int(s);i--)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define all(a) (a).begin(),(a).end()
#define dforn(i,n) dforsn(i,0,n)
#define forn(i,n) forsn(i,0,n)
#define si(a) int((a).size())
#define pb emplace_back
#define mp make_pair
#define snd second
#define fst first
#define endl '\n'
using pii = pair<int,int>;
using vi = vector<int>;
using ll = long long;
struct DSU {
vi par;
DSU(int n): par(n) { iota(all(par), 0); }
int find(int u) { return par[u] == u ? u : par[u] = find(par[u]); }
bool join(int u, int v) {
if ((u = find(u)) == (v = find(v))) return false;
return par[v] = u, true;
}
};
const int N = 200, M = 1e4;
int n, m, A, B, sumT, sumC;
int t[M], c[M], mst[N];
int src[M], dst[M];
ll mn = 1e18;
pii ids[M];
struct Point {
int x, y;
bool collinear(const Point &p1, const Point &p2) {
return ll(p2.y - p1.y) * (x - p1.x) == ll(y - p1.y) * (p2.x - p1.x);
}
};
// Minimize a * sumT + b * sumC = v
Point optimize(int a, int b) {
forn(i, m) ids[i] = {a*t[i] + b*c[i], i};
sort(ids, ids + m);
sumT = 0, sumC = 0;
int pos = 0;
DSU dsu(n);
forn(i, m) {
int id = ids[i].snd;
if (dsu.join(src[id], dst[id]))
sumT += t[id], sumC += c[id], mst[pos++] = id;
}
ll v = ll(sumT) * sumC;
if (v < mn) mn = v, A = a, B = b;
return {sumC, sumT};
}
void computeConvexHull(const Point &p1, const Point &p2) {
Point p = optimize(p2.x - p1.x, p1.y - p2.y);
if (p.collinear(p1, p2)) return;
computeConvexHull(p1, p), computeConvexHull(p, p2);
}
int main() {
fastio;
cin >> n >> m;
forn(i, m) cin >> src[i] >> dst[i] >> t[i] >> c[i];
computeConvexHull(optimize(0, 1), optimize(1, 0));
optimize(A, B);
cout << sumT << ' ' << sumC << endl;
forn(i, n-1) cout << src[mst[i]] << ' ' << dst[mst[i]] << endl;
return 0;
}
