#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define endl '\n'
vector<vector<pair<int, ll>>>graph, creat;
vector<bool>vis;
vector<int>sign;
map<pair<int, int>, bool>eg;
map<pair<int, int>, pair<ll, ll>>as;
vector<pair<ll, pair<int, int>>>price;
vector<pair<int, int>>out;
int num = 0;
ll sum1 = 0, sum2 = 0;
void dfs(int x){
vis[x] = 1;
sign[x] = num;
for(int i = 0; i < creat[x].size() ; i++){
auto [ind, cost] = creat[x][i];
if(!vis[ind]){
sign[ind] = num;
dfs(ind);
}
}
}
void ans(int x){
vis[x] = 1;
for(int i = 0; i < creat[x].size(); i++){
auto [ind, cost] = creat[x][i];
if(!vis[ind]){
out.push_back({x, ind});
sum1 += as[{x, ind}].first;
sum2 += as[{x, ind}].second;
ans(ind);
}
}
}
int main(){
int n, m; cin >> n >> m;
graph.resize(n+1); creat.resize(n+1); vis.resize(n+1, false); sign.resize(n+1);
for(int i = 0; i < m; i++){
int u, v, t, c; cin >> u >> v >> t >> c;
as[{u, v}] = {t, c};
as[{v, u}] = {t, c};
graph[u].push_back({v, t*c});
graph[v].push_back({u, t*c});
}
for(int i = 0; i < n; i++){
pair<int, ll> r = {0, INT_MAX};
for(int j = 0; j < graph[i].size(); j++){
auto [x, y] = graph[i][j];
if(r.second > y){
r = {x, y};
}
}
creat[i].push_back({r.first, r.second});
creat[r.first].push_back({i, r.second});
}
// for(int i = 0; i < n; i++){
// for(int j = 0; j < creat[i].size(); j++){
// cout << i << " " << creat[i][j].first << " " << creat[i][j].second << endl;
// }
// }
for(int i = 0; i < n; i++){
if(!vis[i]){
num++;
dfs(i);
}
}
for(int i = 0; i < n ; i++){
for(int j = 0; j < creat[i].size(); j++){
auto [ind, cost] = creat[i][j];
eg[{i, ind}] = 1;
eg[{ind, i}] = 1;
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < graph[i].size(); j++){
auto [ind, cost] = graph[i][j];
if(eg[{i, ind}] == 0){
price.push_back({cost, {i, ind}});
}
}
}
sort(price.begin(), price.end());
// for(int i = 0; i < price.size(); i++){
// cout << price[i].first << " " << price[i].second.first << " " << price[i].second.second << endl;
// }
if(num > 1){
for(int i = 0; i < price.size() ; i++){
int x = price[i].second.first, y = price[i].second.second;
ll cost = price[i].first;
if(sign[x] != sign[y]){
creat[x].push_back({y, cost});
creat[y].push_back({x, cost});
num = sign[x];
fill(vis.begin(), vis.end(), false);
dfs(x);
}
bool flag = 1;
for(int i = 0; i < n ; i++){
if(!vis[i]) flag = 0;
}
if(flag) break;
}
}
fill(vis.begin(), vis.end(), false);
ans(0);
cout << sum1 << " " << sum2 << endl;
for(int i = 0; i < out.size(); i++){
cout << out[i].first << " " << out[i].second << endl;
}
}
//6 6
//3 2 1 1
//4 1 2 1
//5 0 1 1
//0 1 5 1
//2 0 2 2
//3 4 3 1
