// Author: Ivan Teo
// Created: Sun May 12 18:10:20 2024
#define TASKNAME "timeismoney"
#include <bits/stdc++.h>
using namespace std;
#define fore(i, a, b) for (int i = (a); i <= (b); i++)
#define int long long
using vi = vector<int>;
using ii = pair<int, int>;
#define pb emplace_back
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) v.begin() + 1, v.end()
#define alll(v) v.begin(), v.end()
#define db(x) cerr << "[" << #x << " = " << x << "]"
#define el cerr << "\n=============================\n"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r)
{
assert(l <= r);
return uniform_int_distribution<int> (l, r)(rng);
}
using ld = long double;
using Edge = tuple<ld, int, int, int>;
const int N = 255;
const int M = 1e4 + 5;
int n, m, x[M], y[M], t[M], c[M], b[M];
Edge e[M];
namespace dsu
{
int p[N];
void init()
{
memset(p, -1, sizeof(p));
}
int find(int u)
{
return p[u] < 0 ? u : p[u] = find(p[u]);
}
bool merge(int u, int v)
{
u = find(u);
v = find(v);
if (u == v) return 0;
if (p[u] > p[v]) swap(u, v);
p[u] += p[v];
p[v] = u;
return 1;
}
}
int T, C;
int get(ld s)
{
dsu::init();
fore(i, 1, m) e[i] = {t[i] *s + (255.0 - s) *c[i], x[i] + 1, y[i] + 1, i};
sort(e + 1, e + 1 + m);
T = 0, C = 0;
fore(i, 1, m)
{
auto [w, u, v, id] = e[i];
if (dsu::merge(u, v)) T += t[id], C += c[id], b[id] = 1;
else b[id] = 0;
}
return T * C;
}
void tenarySearch()
{
long double st = 0, dr = 255.0;
while((dr - st) > 1e-7)
{
long double m1 = (2 * st + dr) / 3;
long double m2 = (st + 2 * dr) / 3;
if(get(m1) < get(m2)) dr = m2;
else st = m1;
}
get(st);
cout << T << ' ' << C << '\n';
fore(i, 1, m) if (b[i]) cout << x[i] << ' ' << y[i] << '\n';
}
void solve()
{
cin >> n >> m;
fore(i, 1, m) cin >> x[i] >> y[i] >> t[i] >> c[i];
tenarySearch();
// fore(i, 1, 255) cout << i << ' ' << get(i) << '\n';
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
if (fopen("in", "r"))
freopen("in", "r", stdin);
if (fopen(TASKNAME ".inp", "r"))
{
freopen(TASKNAME ".inp", "r", stdin),
freopen(TASKNAME ".out", "w", stdout);
}
int tc = 1;
// cin >> tc;
while (tc--)
solve();
return 0;
}
