#include <bits/stdc++.h>

using namespace std;

const int N=200005;
int t[N],h[N];

struct Pair{
    int x,y,c;
} v[N],sol[N];

bool cmp(Pair a, Pair b){
    return a.c<b.c;
}

int Find(int x){
    if(x==t[x]) return x;
    t[x]=Find(t[x]);
    return t[x];
}

void Union(int x, int y){
    if(h[x]==h[y]){
        t[y]=x;
        h[x]++;
    }
    else{
        if(h[x]>h[y]) t[y]=x;
        else t[x]=y;
    }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    int n,m,i,j,a,b,c,s=0,cnt=0;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        v[i]={a,b,c};
    }
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=n;i++) t[i]=i;
    //for(int i=1;i<=m;i++) printf("%d %d %d\n",v[i].x,v[i].y,v[i].c);

    for(int i=1;i<=m;i++){
        a=Find(v[i].x);
        b=Find(v[i].y);
        if(a!=b){
            Union(a,b);
            s+=v[i].c;
            sol[++cnt]=v[i];
        }
        if(cnt==n-1) break;
    }

    printf("%d\n%d\n",s,n-1);
    for(int i=1;i<n;i++) printf("%d %d\n",sol[i].x,sol[i].y);


    return 0;
}