#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
struct Point {
int x, y;
Point() : x(0), y(0) {}
Point (int a, int b) : x(a), y(b) {}
Point operator+ (const Point &o) const { return Point(x + o.x, y + o.y); }
Point operator- (const Point &o) const { return Point(x - o.x, y - o.y); }
friend int dot (const Point &a, const Point &b) { return a.x * b.x + a.y * b.y; }
friend int cross (const Point &a, const Point &b) { return a.x * b.y - a.y * b.x; }
friend istream& operator>> (istream &inp, Point &p) { return inp >> p.x >> p.y, inp; }
friend ostream& operator<< (ostream &oup, const Point &p) {
return oup << "(" << p.x << ", " << p.y << ")", oup;
}
};
struct Line {
int A, B, C;
Line() : A(0), B(0), C(0) {}
Line (Point a, Point b) : A(b.y - a.y), B(a.x - b.x), C(cross(a, b)) {}
bool onLine (const Point &p) { return A * p.x + B * p.y == C; }
};
struct DSU {
vector<int> lab;
DSU (int sz) : lab(sz + 1, -1) {}
int get (int u) {
if (lab[u] < 0) return u;
return lab[u] = get(lab[u]);
}
bool unite (int a, int b) {
a = get(a), b = get(b);
if (a == b) return false;
if (-lab[a] < -lab[b]) swap(a, b);
lab[a] += lab[b], lab[b] = a;
return true;
}
};
const int mn = 1e4 + 4;
struct Edge {
int a, b, timeCost, moneyCost;
Edge() : a(0), b(0), timeCost(0), moneyCost(0) {}
Edge (int a, int b, int t, int m) : a(a), b(b), timeCost(t), moneyCost(m) {}
friend istream& operator>> (istream &inp, Edge &e) {
return inp >> e.a >> e.b >> e.timeCost >> e.moneyCost, inp;
}
} edges[mn];
int n, m, ans = INT_MAX;
int optAlpha, optBeta;
Point returnMst (int alpha, int beta) {
auto cost = [&] (const Edge &a) { return alpha * a.timeCost + beta * a.moneyCost; };
auto cmp = [&] (const Edge &a, const Edge &b) { return cost(a) < cost(b); };
sort(edges, edges + m, cmp);
int sumTime = 0, sumMoney = 0;
DSU dsu(n);
for (int i = 0; i < m; i++)
if (dsu.unite(edges[i].a, edges[i].b))
sumTime += edges[i].timeCost, sumMoney += edges[i].moneyCost;
if (sumTime * sumMoney < ::ans)
::ans = sumTime * sumMoney, optAlpha = alpha, optBeta = beta;
return Point(sumTime, sumMoney);
}
void solve (const Point &a, const Point &b) {
Line curLine(a, b);
Point tryPoint = returnMst(curLine.A, curLine.B);
// cout << "solve " << a << " " << b << " found " << tryPoint << "\n";
if (!curLine.onLine(tryPoint))
solve(a, tryPoint), solve(tryPoint, b);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// read input
cin >> n >> m;
for (int i = 0; i < m; i++) cin >> edges[i];
// find optimal solution
solve(returnMst(0, 1), returnMst(1, 0));
// reconstruct solution
int sumTime = 0, sumMoney = 0;
auto cost = [&] (const Edge &a) { return optAlpha * a.timeCost + optBeta * a.moneyCost; };
auto cmp = [&] (const Edge &a, const Edge &b) { return cost(a) < cost(b); };
sort(edges, edges + m, cmp);
DSU dsu(n);
vector<pii> edgeList;
for (int i = 0; i < m; i++) {
if (!dsu.unite(edges[i].a, edges[i].b)) continue;
edgeList.emplace_back(edges[i].a, edges[i].b);
sumTime += edges[i].timeCost;
sumMoney += edges[i].moneyCost;
}
cout << sumTime << " " << sumMoney << "\n";
for (auto [a, b] : edgeList)
cout << a << " " << b << "\n";
return 0;
}
