#include <bits/stdc++.h>
// #include <iostream>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define sz(x) int((x).size())
#define all(a) begin(a), end(a)
#define pll pair<long long, long long>
#define vb vector<bool>
#define vll vector<long long>
#define vvll vector<vector<long long> >
#define vpl vector< pair<long long, long long> >
#define f(i,s,e) for(long long int i = s; i < e; i++)
#define cf(i,s,e) for(long long int i = s; i <= e; i++)
#define rf(i,s,e) for(long long int i = s; i >= e; i--)
#define print(a) for(auto x : a) cout << x << " " <<endl;
#define printp(a) for(auto x : a) cout << x.first << " " << x.second <<endl;
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;
inline ll read() {ll x = 0, fh = 1; char ch = getchar(); while(!isdigit(ch)) {if (ch == '-') fh = -1; ch = getchar();} while (isdigit(ch)) {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();} return x*fh;}
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
ll t, n, m, k, a, b, tot;
string s;
ll edges[10009][4];
bool used[10009], connect[209];
void solve() {
cin >> n >> m;
f(i, 0, m) {
cin >> a >> b >> t >> k;
edges[i][0] = a;
edges[i][1] = b;
edges[i][2] = t;
edges[i][3] = k;
}
ll time = 0, cost = 0;
f(i, 0, n-1) {
ll idx = 0, mn = LLONG_MAX;
f(j, 0, m) {
if (!used[j]) {
if (!connect[edges[j][0]] && !connect[edges[j][1]] && time > 0) continue;
if ((time + edges[j][2]) * (cost + edges[j][3]) < mn) {
mn = (time + edges[j][2]) * (cost + edges[j][3]);
idx = j;
}
}
}
used[idx] = 1;
connect[edges[idx][0]] = 1;
connect[edges[idx][1]] = 1;
time += edges[idx][2];
cost += edges[idx][3];
}
cout << time << " " << cost <<endl;
f(i, 0, m) if (used[i]) cout << edges[i][0] << " " << edges[i][1] <<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
