#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct muchie
{
    int i,j,ct;
}h[400005],h1[200005];
int f[200005],g[200005],k,i,x,m,j,ct,ok;
bool sortare(muchie x,muchie y)
{
    return x.ct<y.ct;
}
int cauta(int x)
{
    int k,i,m;
    for(k=x;f[k]!=k;k=f[k]);
    for(i=x;f[i]!=i;i=f[i])
        f[i]=k;
    return k;
}
void unire(int x,int y)
{
    int k,i,m;
    if(g[x]<g[y])
        swap(x,y);
    f[y]=x;
    g[x]+=g[y];
    g[y]=g[x];
    if(x==y)
        g[x]++;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&x,&m);
    for(k=1;k<=x;k++)
    {
        f[k]=k;
        g[k]=1;
    }
    for(k=1;k<=m;k++)
        scanf("%d%d%d",&h[k].i,&h[k].j,&h[k].ct);
    sort(h+1,h+m+1,sortare);
    for(k=1,j=1,ct=0;k<=m;k++)
    {
        if(cauta(h[k].i)!=cauta(h[k].j))
        {
            ct+=h[k].ct;
            unire(cauta(h[k].i),cauta(h[k].j));
            h1[j]=h[k];
            j++;
            if(j==x)
                break;
        }
    }
    printf("%d\n%d\n",ct,x-1);
    for(k=1;k<=x-1;k++)
        printf("%d %d\n",h1[k].i,h1[k].j);

    return 0;
}