// AI Generated code for testing if it's right, I already solved it before a few years ago but I wanted to see if AI could solve it
/*
* Problem: Time is Money (Balkan Olympiad in Informatics 2011)
* Method: Primal-Dual / Geometry on Convex Hull
* Complexity: O(K * M * alpha(N)), where K is the number of hull vertices (usually small)
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
// Data structures
struct Edge {
int u, v, t, c, id;
};
struct Point {
long long x, y; // x = sumTime, y = sumMoney
};
int N, M;
vector<Edge> edges;
// Global variables to store the best solution found so far
long long minV = -1;
Point bestPoint;
// We store the coefficients (A, B) that produced the best solution
// so we can reconstruct the tree at the end for printing.
long long bestA = 0, bestB = 0;
// Union-Find (DSU) structures
vector<int> parent;
void dsu_init(int n) {
parent.resize(n);
for (int i = 0; i < n; ++i) parent[i] = i;
}
int dsu_find(int i) {
if (parent[i] == i)
return i;
return parent[i] = dsu_find(parent[i]);
}
void dsu_union(int i, int j) {
int root_i = dsu_find(i);
int root_j = dsu_find(j);
if (root_i != root_j) {
parent[root_i] = root_j;
}
}
// Kruskal's Algorithm with dynamic weights A*t + B*c
// Returns the (SumTime, SumMoney) of the resulting tree
Point getMST(long long A, long long B) {
// Sort edges based on current weights
sort(edges.begin(), edges.end(), [A, B](const Edge& a, const Edge& b) {
long long valA = A * a.t + B * a.c;
long long valB = A * b.t + B * b.c;
return valA < valB;
});
dsu_init(N);
long long sumT = 0;
long long sumC = 0;
int edgesCount = 0;
for (const auto& e : edges) {
if (dsu_find(e.u) != dsu_find(e.v)) {
dsu_union(e.u, e.v);
sumT += e.t;
sumC += e.c;
edgesCount++;
}
}
// Update global minimum if this tree is better
long long currentV = sumT * sumC;
if (minV == -1 || currentV < minV || (currentV == minV && sumT < bestPoint.x)) {
minV = currentV;
bestPoint = {sumT, sumC};
bestA = A;
bestB = B;
}
return {sumT, sumC};
}
// Recursive function to find hull points
void solve(Point p1, Point p2) {
// Calculate weights perpendicular to the line segment p1-p2
// We use absolute differences for positive weights
long long A = abs(p1.y - p2.y);
long long B = abs(p1.x - p2.x);
// Run MST with new weights
Point pNew = getMST(A, B);
// Check if pNew is effectively the same as endpoints (prevents infinite loops)
if (pNew.x == p1.x && pNew.y == p1.y) return;
if (pNew.x == p2.x && pNew.y == p2.y) return;
// Geometry check: Is pNew strictly "below" the segment p1-p2?
// We check using cross product logic.
// Vector P1->P2: (p2.x - p1.x, p2.y - p1.y)
// Vector P1->New: (pNew.x - p1.x, pNew.y - p1.y)
// Cross product (x1*y2 - x2*y1). If < 0, it's to the right (below/concave).
long long cross_product = (p2.x - p1.x) * (pNew.y - p1.y) - (p2.y - p1.y) * (pNew.x - p1.x);
// If cross_product >= 0, the point is not improving the lower hull
if (cross_product >= 0) return;
// Recurse
solve(p1, pNew);
solve(pNew, p2);
}
int main() {
// Optimize I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (fopen("timeismoney.in", "r")) {
freopen("timeismoney.in", "r", stdin);
freopen("timeismoney.out", "w", stdout);
}
cin >> N >> M;
for (int i = 0; i < M; ++i) {
int u, v, t, c;
cin >> u >> v >> t >> c;
edges.push_back({u, v, t, c, i});
}
// Step 1: Find extreme points
// Minimize only Time (Weight: 1*t + 0*c)
Point pTime = getMST(1, 0);
// Minimize only Money (Weight: 0*t + 1*c)
Point pMoney = getMST(0, 1);
// Step 2: Start recursive search between the extremes
solve(pTime, pMoney);
// Step 3: Output
cout << bestPoint.x << " " << bestPoint.y << endl;
// To print the actual edges, we re-run the MST one last time
// using the cached best weights to reconstruct the specific tree.
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
long long valA = bestA * a.t + bestB * a.c;
long long valB = bestA * b.t + bestB * b.c;
return valA < valB;
});
dsu_init(N);
for (const auto& e : edges) {
if (dsu_find(e.u) != dsu_find(e.v)) {
dsu_union(e.u, e.v);
cout << e.u << " " << e.v << endl;
}
}
return 0;
}
