//disjoint clasic
#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int i, j, n, m, op, total, x[450000], y[450000], cost[450000], poz[450000], T[450000], Rang[450000], xa[450000], ya[450000], g;
 

int Radacina(int k){
    if(T[k] == k)
        return k;
    else
    {
        int r = Radacina(T[k]);
        T[k] = r;
        return r;
    }
}

void Unire(int k, int p)
{
    int rk = Radacina(k), rp = Radacina(p);
    if(rk != rp)
    {
        if(Rang[rk] > Rang[rp])
            T[rp] = rk;
        else
        {
            T[rk] = rp;
            if(Rang[rk] == Rang[rp])
                Rang[rp] ++;
        }
    }
    
}




int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++){
        Rang[i]=1;
        T[i]=i;
    }
    
    for(i=1;i<=m;i++)
    {
        fin>>x[i]>>y[i]>>cost[i];
        poz[cost[i]+1001]=i;
        
    }
    
    sort(cost+1 , cost+m+1);

    
    for(i=1;i<=m;i++){
        if(Radacina(x[poz[cost[i]+1001]])!=Radacina(y[poz[cost[i]+1001]])){
            Unire(x[poz[cost[i]+1001]] , y[poz[cost[i]+1001]]);
            xa[++g]=x[poz[cost[i]+1001]];
            ya[g]=y[poz[cost[i]+1001]];
            total+=cost[i];
        }
    }
    
    fout<<total<<endl;
    fout<<n-1<<endl;
    for(i=1;i<=g;i++){
        fout<<xa[i]<<" "<<ya[i]<<endl;
    }
    
}