//
// main.cpp
// GeneralCompetitiveProgramming
//
// Created by Ali AlSalman on 12/07/2023.
//
#include <bits/stdc++.h>
//#define INTERACTIVE
//#define TESTCASES
#ifndef INTERACTIVE
#define endl '\n'
#endif
template<typename T>
using vec = std::vector<T>;
using namespace std;
typedef vec<pair<int, int>> mst_t;
struct mst_value_t {
long long cost, time;
};
struct mst_query_t {
mst_t mst;
mst_value_t value;
};
bool mask = true;
vec<bool> vis;
vec<vec<array<int, 3>>> adj;
mst_query_t mst(long long a, long long b, bool construct = false) {
mst_t tree;
long long sum_c = 0, sum_t = 0;
auto cmp = [a, b](array<long long, 4> lhs, array<long long, 4> rhs) -> bool {
return a * lhs[2] + b * lhs[3] > a * rhs[2] + b * rhs[3];
};
priority_queue<
array<long long, 4>,
vec<array<long long, 4>>,
decltype(cmp)
> q(cmp); q.push({0, -1, 0, 0});
while (!q.empty()) {
auto [u, v, _c, _t] = q.top(); q.pop();
if (vis[u] == mask) continue;
vis[u] = !vis[u]; if (construct && 0 <= u && 0 <= v) tree.push_back({u, v});
sum_c += _c; sum_t += _t;
for (auto [c, c_c, c_t] : adj[u]) if (vis[c] != mask) {
q.push({c, u, c_c, c_t});
}
}
mask = !mask;
return {tree, {sum_c, sum_t}};
}
struct mst_producer_t {
long long cost_factor, time_factor;
};
struct point_t { // the point is identified by it's `mst_value`; x = cost, y = time.
mst_producer_t producer;
mst_value_t mst_value;
long long x() const { return mst_value.cost; }
long long y() const { return mst_value.time; }
bool operator ==(const point_t &other) const {
return x() == other.x() && y() == other.y();
}
};
point_t cnvx(point_t a, point_t b) {
auto min_p = [](point_t a, point_t b) {
if (a.x() * a.y() <= b.x() * b.y()) return a;
return b;
};
point_t p = {
{ a.y() - b.y(), b.x() - a.x() },
mst(a.y() - b.y(), b.x() - a.x()).value
};
if (p == a || p == b) return min_p(a, b);
return min_p(cnvx(a, p), cnvx(p, b));
}
void solve() {
int n, m;
cin>>n>>m; vis.resize(n); adj.resize(n);
while (m--) {
int a, b, c, d;
cin>>a>>b>>c>>d;
adj[a].push_back({b, c, d});
adj[b].push_back({a, c, d});
}
auto c_point = point_t {
{1, 0},
mst(1, 0).value
};
auto t_point = point_t {
{0, 1},
mst(0, 1).value
};
auto opt = cnvx(c_point, t_point);
cout<<opt.mst_value.cost<<" "<<opt.mst_value.time<<endl;
for (auto [u, v] : mst(opt.producer.cost_factor, opt.producer.time_factor, true).mst) {
cout<<u<<" "<<v<<endl;
}
}
int main() {
#ifndef INTERACTIVE
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#endif
int t = 1;
#ifdef TESTCASES
cin>>t;
#endif
while (t--) solve();
}
