#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define ii pair<int,int>
#define FOR(i,a,b) for(int i = (a),_b=(b); i<=_b; ++i)
#define FORD(i,a,b) for(int i = (a),_b=(b); i>=_b; --i)
template<class X,class Y>
bool maximize(X &x,Y y){
if (x<y) return x=y,true; else return false;
}
template<class X,class Y>
bool minimize(X &x,Y y){
if (x>y) return x=y,true; else return false;
}
const int N = (int)10000;
int n , m;
int u[N+2] , v[N+2] , c[N+2] , t[N+2];
struct Point{
LL a,b;
long double edg;
Point() {};
Point(LL a,LL b,long double heso) : a(a) , b(b) , edg(heso) {};
LL F(){
return a*b;
}
bool operator == (const Point &other) const{
return other.a == a && other.b == b;
}
};
long double slope(Point x,Point y){
return (long double)(y.b - x.b) / (x.a - y.a);
}
struct EDGE{
int u,v;
LL t,c;
long double cost;
bool operator < (const EDGE&other) const{
if (cost != other.cost) return cost<other.cost;
return t*c < other.t*other.c;
}
};
const long double eps = 1e-9;
const LL inf = (LL)1e18;
int par[N+2] , sz[N+2] = {};
int Find(int u){
return par[u] == u ? par[u] : par[u] = Find(par[u]);
}
bool unite(int u,int v){
u = Find(u) , v = Find(v);
if (u==v) return false;
if (sz[u] < sz[v]) swap(u,v);
par[v] = u , sz[u] += sz[v];
return true;
}
Point MST(long double heso , bool write = false){
vector<EDGE> edg;
FOR(i,1,m){
edg.push_back({u[i] , v[i] , t[i] , c[i] , heso * t[i] + c[i]});
}
sort(edg.begin(),edg.end());
FOR(i,1,n) par[i] = i , sz[i] = 1;
LL sum_time = 0 , sum_money = 0;
Point sum = Point(0,0,heso);
for(int i = 0; i < edg.size(); ++i){
if (unite(edg[i].u , edg[i].v)){
sum.a += edg[i].t;
sum.b += edg[i].c;
if (write) cout<<edg[i].u-1<<' '<<edg[i].v-1<<'\n';
}
}
return sum;
}
vector<Point>hull;
void dnc(Point x,Point y){
long double slope_k = 0;
if (y.b - x.b != 0){
slope_k = slope(x,y);
}
else slope_k = LLONG_MAX;
Point nxt_p = MST(slope_k);
LL cross_product = (LL)(y.a - x.a) * (nxt_p.b - x.b) - (LL)(y.b - x.b) * (nxt_p.a - x.a);
if (cross_product > 0){
dnc(x,nxt_p);
dnc(nxt_p,y);
hull.push_back(nxt_p);
}
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0);
#define name "main"
if (fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
cin>>n>>m;
FOR(i,1,m) {
cin >> u[i] >> v[i] >> t[i] >> c[i];
++u[i] , ++v[i];
}
Point min_time = MST(0) , min_money = MST(LLONG_MAX);
hull.push_back(min_time);
if (!(min_time == min_money)){
hull.push_back(min_money);
dnc(min_time , min_money);
}
long double res = 0;
LL ans = inf;
LL sum_time = 0 , sum_money = 0;
for(auto&x:hull){
if (minimize(ans , x.a*x.b)){
sum_time = x.a , sum_money = x.b;
res = x.edg;
}
}
cout<<sum_time << ' '<<sum_money<<'\n';
MST(res,true);
return 0;
}
