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

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

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


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] ++;
        }
    }
    
}

bool compare(student a, student b){
    if(a.cost<b.cost){
        return 1;
    }else{
        return 0;
    }
}



int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++){
        Rang[i]=1;
        T[i]=i;
    }
    
    student v[450000];
    
    for(i=1;i<=m;i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].cost;
    }
    
    sort(v+1 , v+m+1, compare);

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