#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=205;
int N,M;
vector<array<int,3>> adj[MX];
ll w[10005];
array<ll,4> e[10005];
struct DSU {
int par[MX];
int find(int v) {
return par[v]==v?v:par[v]=find(par[v]);
}
bool merge(int u, int v) {
u=find(u), v=find(v);
if(u==v) return false;
par[u]=v;
return true;
}
void prep() {
for(int i=0;i<MX;i++) par[i]=i;
}
} ds;
#define pt pair<ll,ll>
#define px first
#define py second
ll optV=0, optT=0, optC=0;
vector<pair<ll,ll>> optE, cur;
ll area(pt a, pt b, pt c) {
return (b.px-a.px)*(c.py-b.py)-(c.px-b.px)*(b.py-a.py);
}
vector<int> ord;
pt kruskal() {
cur.clear();
sort(ord.begin(),ord.end(),[&](int i, int j){
return w[i]<w[j];
});
ll st=0, sc=0;
ds.prep();
for(auto x:ord) {
auto [u,v,t,c]=e[x];
if(ds.merge(u,v)) {
cur.push_back({u,v});
st+=t;
sc+=c;
}
}
return {st,sc};
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>N>>M;
for(int i=0;i<M;i++) {
int x,y,t,c;
cin>>x>>y>>t>>c;
adj[x].push_back({y,t,c});
adj[y].push_back({x,t,c});
e[i]={x,y,t,c};
}
for(int i=0;i<M;i++) ord.push_back(i);
// time on x axis cost on y axis
// get point A -> minimize x axis
for(int i=0;i<M;i++)
w[i]=e[i][2];
pt A=kruskal();
optV=A.px*A.py;
optT=A.px;
optC=A.py;
optE=cur;
// get point B -> minimize y axis
for(int i=0;i<M;i++)
w[i]=e[i][3];
pt B=kruskal();
if(B.px*B.py<optV) {
optV=B.px*B.py;
optT=B.px;
optC=B.py;
optE=cur;
}
vector<pair<pt,pt>> stk;
stk.push_back({A,B});
while(!stk.empty()) {
auto [A,B]=stk.back(); stk.pop_back();
// assing new weight based on Py(Bx - Ax) + Px(Ay - By)
// y axis is cost, x axis is time
for(int i=0;i<M;i++)
w[i]=e[i][3]*(B.px-A.px) + e[i][2]*(A.py-B.py);
pt P=kruskal();
// isn't on the lower convex hull
if(area(A,B,P)>=0) continue;
if(P.px*P.py<optV) {
optV=P.px*P.py;
optT=P.px;
optC=P.py;
optE=cur;
}
stk.push_back({A,P});
stk.push_back({P,B});
}
cout<<optT<<" "<<optC<<'\n';
for(auto [u,v]:optE) {
cout<<u<<" "<<v<<'\n';
}
}
