#include<bits/stdc++.h>
using namespace std;
const int siz = 205;
int p[siz],sz[siz];
int findp(int a){
if (p[a] == a) return a;
return p[a] = findp(p[a]);
}
void unite(int a, int b){
if (sz[a] < sz[b]) swap(a,b);
p[b] = a;
sz[a] += sz[b];
}
int gcd(int a, int b){
if (a < b) swap(a,b);
return b?gcd(b,a%b):a;
}
int I,J;
bool cmp(pair<pair<int,int>,pair<int,int>> & a, pair<pair<int,int>,pair<int,int>> &b){
return a.second.first*I+a.second.second*J < b.second.first*I+b.second.second*J;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int n,m; cin >> n >> m;
vector<pair<pair<int,int>,pair<int,int>>> v(m);
pair<pair<int,int>,vector<pair<int,int>>> ans;
for (int i = 0;i<m;i++) cin >> v[i].first.first >> v[i].first.second >> v[i].second.first >> v[i].second.second;
long long best = LLONG_MAX;
for (I = 1;I<65;I++){
for (J = 1;J<65;J++){
if (I != 1 && J != 1 && gcd(I,J) == 1) continue;
for (int i = 0;i<n;i++) {p[i] = i;sz[i] = 1;}
sort(v.begin(),v.end(),cmp);
int cnt1 = 0,cnt2 = 0;
vector<pair<int,int>> e;
for (int i = 0;i<m;i++){
auto [a,b] = v[i].first;
a = findp(a);
b = findp(b);
if (a == b) continue;
e.push_back(v[i].first);
unite(a,b);
cnt1 += v[i].second.first;
cnt2 += v[i].second.second;
}
if (1LL*cnt1*cnt2 < best){
best = 1LL*cnt1*cnt2;
ans.first.first = cnt1;
ans.first.second = cnt2;
ans.second.clear();
for (auto &a:e) ans.second.push_back(a);
}
}
}
cout << ans.first.first << ' ' << ans.first.second << '\n';
for (auto [a,b]:ans.second) cout << a << ' ' << b << '\n';
return 0;
}
