#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
// 邊的結構，增加了 id 來記錄原始索引
struct Edge {
int u, v, t, c;
int id;
long double weight; // 使用浮點數來計算加權後的權重
};
// 代表一個解 (一棵生成樹) 的結構
struct Solution {
long long time;
long long money;
vector<int> edge_ids; // 記錄構成此樹的邊的 ID
// 用於比較兩個解是否相同
bool operator==(const Solution& other) const {
return time == other.time && money == other.money;
}
};
int n;
vector<Edge> initial_edges;
vector<int> parent;
vector<Solution> hull_points; // 儲存所有凸包上的點
int find_set(int i) {
if (parent[i] == i) return i;
return parent[i] = find_set(parent[i]);
}
// Kruskal 演算法，根據指定的 k 值計算 MST
Solution kruskal(long double k) {
for (auto& edge : initial_edges) {
// 核心：根據 k 值計算新的權重
edge.weight = k * edge.t + edge.c;
}
sort(initial_edges.begin(), initial_edges.end(), [](const Edge& a, const Edge& b) {
// 權重相同時，優先選 t*c 較小的 (可選，一種穩定排序策略)
if (a.weight == b.weight) {
return (long long)a.t * a.c < (long long)b.t * b.c;
}
return a.weight < b.weight;
});
parent.assign(n, 0);
for (int i = 0; i < n; ++i) parent[i] = i;
Solution sol = {0, 0};
int edges_count = 0;
for (const auto& edge : initial_edges) {
int root_u = find_set(edge.u);
int root_v = find_set(edge.v);
if (root_u != root_v) {
parent[root_v] = root_u;
sol.time += edge.t;
sol.money += edge.c;
sol.edge_ids.push_back(edge.id); // 記錄邊的原始 ID
edges_count++;
if (edges_count == n - 1) break;
}
}
return sol;
}
// 遞迴函式，尋找凸包頂點
void find_hull(const Solution& p1, const Solution& p2) {
long double k = 0;
// 防止除以零
if (p2.time - p1.time != 0) {
k = -(long double)(p2.money - p1.money) / (p2.time - p1.time);
} else {
// 如果時間相同，斜率為無窮大，對應 k 也為極大值
// 我們要找的是最小化 time 的點，這裡傳入極大 k 即可模擬
k = LLONG_MAX;
}
Solution p3 = kruskal(k);
// 判斷點 p3 是否在 p1 和 p2 構成的線段之外
// 透過叉積判斷，如果叉積 > 0，則 p3 在線段下方，是新的凸包點
// (p2-p1) x (p3-p1) > 0
// (p2.t-p1.t)*(p3.m-p1.m) - (p2.m-p1.m)*(p3.t-p1.t) > 0
long double cross_product = (long double)(p2.time - p1.time) * (p3.money - p1.money) - (long double)(p2.money - p1.money) * (p3.time - p1.time);
// 考慮浮點數誤差，用一個很小的 epsilon
if (cross_product > 1e-9) {
find_hull(p1, p3);
hull_points.push_back(p3);
find_hull(p3, p2);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int m;
while (cin >> n >> m) {
initial_edges.clear();
hull_points.clear();
vector<Edge> original_input_edges; // 為了最後輸出用
for (int i = 0; i < m; ++i) {
int u, v, t, c;
cin >> u >> v >> t >> c;
initial_edges.push_back({u, v, t, c, i});
}
original_input_edges = initial_edges;
Solution p_min_money = kruskal(0);
Solution p_min_time = kruskal(LLONG_MAX);
hull_points.push_back(p_min_money);
if (!(p_min_time == p_min_money)) {
find_hull(p_min_money, p_min_time);
hull_points.push_back(p_min_time);
}
long double min_product = -1;
Solution best_solution;
for (const auto& sol : hull_points) {
long double product = (long double)sol.time * sol.money;
if (min_product < 0 || product < min_product) {
min_product = product;
best_solution = sol;
}
}
// --- 輸出部分 ---
cout << best_solution.time << " " << best_solution.money << "\n";
for (int edge_id : best_solution.edge_ids) {
// edge_id 就是原始邊在 original_input_edges 中的索引
const Edge& edge_to_print = original_input_edges[edge_id];
cout << edge_to_print.u << " " << edge_to_print.v << "\n";
}
}
return 0;
}
