#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
#define sz(x) (int)x.size()
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 2e5+5, INF = 1e9;
int n, m;
struct State{
int to, time, cost, from;
};
vector<State> arr[MAXN], output;
pii edges[MAXN];
pair<ll, ll> curMin = {60000, 60000};
void prims(int a, int b){
auto cmp = [&](State& x, State& y){
return x.time * a + x.cost * b > y.time * a + y.cost * b;
};
priority_queue<State, vector<State>, decltype(cmp)> pq(cmp);
vector<int> cost(n, INF);
vector<bool> used(n);
vector<State> mst;
cost[0] = 0;
pq.push({0, 0, 0, -1});
while (!pq.empty()){
State cur = pq.top();
pq.pop();
if (used[cur.to]){
continue;
}
used[cur.to] = true;
mst.push_back(cur);
for (State x : arr[cur.to]){
if (x.time * a + x.cost * b < cost[x.to] && !used[x.to]){
cost[x.to] = x.time * a + x.cost * b;
pq.push(x);
}
}
}
ll time = 0, money = 0;
for (State x : mst){
time += x.time;
money += x.cost;
}
if (time * money < curMin.first * curMin.second){
swap(output, mst);
curMin = {time, money};
}
}
signed main(){
cin.tie(0); ios_base::sync_with_stdio(0);
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
cin >> n >> m;
for (int i=0; i<m; i++){
int a, b, t, c;
cin >> a >> b >> t >> c;
edges[i] = {t, c};
arr[a].push_back({b, t, c, a});
arr[b].push_back({a, t, c, b});
}
for (int i=1; i<2000; i++){
prims(uid(1, 51000), uid(1, 51000));
}
cout << curMin.first << " " << curMin.second << "\n";
for (int i=1; i<sz(output); i++){
cout << output[i].from << " " << output[i].to << "\n";
}
}
/**
* Debugging checklist:
* - Reset everything after each TC
* - Integer overflow, index overflow
* - Special cases?
*/
