#include<bits/stdc++.h>
//#define inf 0x3f3f3f3f
//#define int long long
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
#define cin fin
#define cout fout
const int MOD=1e9+9;
//const int mare=1LL*1000000000000000000;
const int mare=1e9+5;
const int nmax=1e7+5;
const int dx[] = { 0,1, 0,-1};
const int dy[] = { 1,0,-1, 0};
int T,n,q,m,x,y,poz,cmax,contor,ans;
int i,j,l,nr,aux,sum,maxx,s,c,rad,rasp,st,dr,mij;
int h[200005],t[200005];
struct muchii
{
    int a;
    int b;
    int cost;
};
muchii e[200005],v[200005];
int find(int k)
{
    if(t[k]==k)
        return k;
    return t[k]=find(t[k]);
}
void uniune(int a, int b)
{
    if(h[a]>h[b])
        t[b]=a;
    else
        if(h[a]<h[b])
            t[a]=b;
        else
        {
            t[a]=b;
            h[b]++;
        }
}
bool cmp1(muchii aa, muchii bb)
{
    if(aa.cost<bb.cost)
        return 1;
    return 0;
}
signed main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        t[x]=x;
        t[y]=y;
        e[i].a=x;
        e[i].b=y;
        e[i].cost=c;
    }
    //cout<<t[0]<<"\n";
    s=0;
    sort(e+1,e+m+1,cmp1);
    int dim=0;
    for(i=1;i<=m;i++)
    {
        cout<<t[e[i].a]<<" "<<t[e[i].b]<<" "<<find(e[i].a)<<" "<<find(e[i].b)<<"\n";
        if(find(e[i].a)!=find(e[i].b))
        {
            s=s+e[i].cost;
            dim++;
            v[dim]=e[i];
            uniune(find(e[i].a),find(e[i].b));
        }
    }
    cout<<s<<"\n";
    cout<<n-1<<"\n";
    for(i=1;i<=dim;i++)
        cout<<v[i].a<<" "<<v[i].b<<"\n";
    fin.close();
    fout.close();
    return 0;
}

/*
5 5
.##..
#....
#.###
.....
#....
 */