#include <bits/stdc++.h>
using namespace std;
struct edge
{
int x,y,t,c;
};
int n,m;
edge a[10005];
vector<pair<int,pair<int,int>>> e;
map<pair<int,int>,int> timp, cost, idx;
struct sol
{
vector<bool> use;
int v,sumtime,summoney;
};
sol ans;
int tt[205],sz[205];
int rep(int x)
{
while (x != tt[x])
x = tt[x];
return x;
}
void join(int x,int y)
{
x = rep(x);
y = rep(y);
if (x == y)
return;
if (sz[x] < sz[y])
swap(x,y);
sz[x] += sz[y];
tt[y] = x;
}
int main()
{
ans.v = ans.sumtime = 1e9;
ans.summoney = 1;
cin >> n >> m;
ans.use.resize(m + 1);
for (int i = 1; i <= m; i++)
{
cin >> a[i].x >> a[i].y >> a[i].t >> a[i].c;
timp[{a[i].x,a[i].y}] = a[i].t;
cost[{a[i].x,a[i].y}] = a[i].c;
idx[{a[i].x,a[i].y}] = i;
}
for (int rata = 1; rata <= 200; rata++)
{
e.clear();
for (int i = 1; i <= m; i++)
{
int x = a[i].x,y = a[i].y;
int cost = a[i].c + rata * a[i].t;
e.push_back({cost,{x,y}});
}
sort(e.begin(),e.end());
for (int i = 0; i < n; i++)
tt[i] = i,sz[i] = 1;
vector<pair<int,int>> luate;
for (auto it : e)
{
if (rep(it.second.first) != rep(it.second.second))
{
luate.push_back(it.second);
join(it.second.first,it.second.second);
}
}
sol cur;
cur.use.resize(m + 1);
cur.summoney = cur.sumtime = 0;
for (auto it : luate)
{
cur.use[idx[it]] = true;
cur.sumtime += timp[it];
cur.summoney += cost[it];
}
cur.v = cur.sumtime * cur.summoney;
if (cur.v < ans.v)
ans = cur;
}
for (int rata = 1; rata <= 200; rata++)
{
e.clear();
for (int i = 1; i <= m; i++)
{
int x = a[i].x,y = a[i].y;
int cost = a[i].c * rata + a[i].t;
e.push_back({cost,{x,y}});
}
sort(e.begin(),e.end());
for (int i = 0; i < n; i++)
tt[i] = i,sz[i] = 1;
vector<pair<int,int>> luate;
for (auto it : e)
{
if (rep(it.second.first) != rep(it.second.second))
{
luate.push_back(it.second);
join(it.second.first,it.second.second);
}
}
sol cur;
cur.use.resize(m + 1);
cur.summoney = cur.sumtime = 0;
for (auto it : luate)
{
cur.use[idx[it]] = true;
cur.sumtime += timp[it];
cur.summoney += cost[it];
}
cur.v = cur.sumtime * cur.summoney;
if (cur.v < ans.v)
ans = cur;
}
cout << ans.sumtime << ' ' << ans.summoney << '\n';
for (int i = 1; i <= m; i++)
if (ans.use[i])
cout << a[i].x << ' ' << a[i].y << '\n';
return 0;
}
