#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>

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

int n,m,i,x,y,c,d[200005],k,tata[200005],sol;
struct arc{
    int x,y,cost;
}a[400005];
bool viz[400005];
int cmp(arc a, arc b){
    return a.cost < b.cost;
}
int parinte(int x){
    while(tata[x]>0)
        x=tata[x];
    return x;
}

int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        a[i].x = x;
        a[i].y = y;
        a[i].cost = c;
    }
    for(i=1;i<=n;i++){
        tata[i]=-1;
    }
    sort(a+1,a+m+1,cmp);
    k=n-1;
    i=1;
    while(k>0){
        x=parinte(a[i].x);
        y=parinte(a[i].y);
        if(x!=y){
                viz[i]=1;
        sol+=a[i].cost;
        if(tata[x]<tata[y]){
            tata[x]+=tata[y];
            tata[y]=x;
        }
        else{
            tata[y]+=tata[x];
            tata[x]=y;
        }
        k--;
        }
      i++;
    }
    fout<<sol<<'\n'<<n-1<<'\n';
    for(i=1;i<=m;i++)
        if(viz[i])
            fout<<a[i].x<<' '<<a[i].y<<'\n';
    return 0;
}