#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
struct store{
int x, y, t, c;
};
int n, m;
vector<store> edges;
ll currVal; int ansT, ansC; vector<pair<int, int>> links;
vector<int> par, sz;
int find(int node){
if (node == par[node]) return node;
return par[node] = find(par[node]);
}
void merge(int a, int b){
a = find(a), b = find(b);
if (sz[a] > sz[b]) swap(a, b);
par[a] = b; sz[b] += sz[a];
}
bool cmp1(store a, store b){
return a.t-((long double)currVal/a.c) < b.t-((long double)currVal/b.c);
}
bool cmp2(store a, store b){
return a.c-((long double)currVal/a.t) < b.c-((long double)currVal/b.t);
}
bool check(int whichCmp){
if (whichCmp == 1) sort(edges.begin(), edges.end(), cmp1);
else sort(edges.begin(), edges.end(), cmp2);
par.resize(n); sz.resize(n, 1); iota(par.begin(), par.end(), 0);
for (int i = 0; i < n; i++) par[i] = i;
ansT = 0, ansC = 0, links.clear();
for (store edge : edges){
if (find(edge.x) != find(edge.y)){
merge(edge.x, edge.y);
ansT += edge.t, ansC += edge.c; links.push_back({edge.x, edge.y});
}
}
return (ll)ansT*(ll)ansC <= currVal;
}
int main(){
cin >> n >> m; edges.resize(m);
for (int i = 0; i < m; i++)
cin >> edges[i].x >> edges[i].y >> edges[i].t >> edges[i].c;
ll low = 0; ll high = ((ll)255*n*255*n)+1;
while (low < high){
currVal = (low+high+1)/2;
if (check(1) or check(2)){
high = currVal-1;
}
else low = currVal;
}
cout<<ansT<<" "<<ansC<<endl;
for (pair<int, int> elem : links)
cout<<elem.first<<" "<<elem.second<<endl;
}
