#include<stdio.h>
#include<algorithm>
using namespace std;
struct muchie
{
    int x,y,c;
} l[401010];
int tata[201010],tip,a,b,h[201010],rez[202020],N,r,S,M;
int find(int x)
{
int R,y;
    R=x;
    while(tata[R]!=R)
        R=tata[R];
    while(tata[x]!=x)
    {
    y=tata[x];
    tata[x]=R;
    x=y;
    }
    return R;
}
int unite(int x,int y)
{
    if(h[x]>h[y])
    {
        tata[y]=x;
    }
    else tata[x]=y;

    if(h[x]==h[y])
        h[y]++;
}
bool cmp(muchie a,muchie b)
{
    return a.c<b.c;
}
int main()
{
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
scanf("%d%d",&N,&M);
for(int i=1;i<=N;++i)
    {
    tata[i]=i;
    h[i]=1;
    }
    for(int i=1;i<=M;++i)
    {
        scanf("%d%d%d",&l[i].x,&l[i].y,&l[i].c);

    }
    sort(l+1,l+M+1,cmp);
    for(int i=1;i<=M;++i)
        {
            if(find(l[i].x)!=find(l[i].y))
            {
                unite(find(l[i].x),find(l[i].y));
                S+=l[i].c;
                rez[++r]=i;
            }
        }
    printf("%d\n%d\n",S,N-1);
        for(int i=1;i<=r;++i)
            printf("%d %d\n",l[rez[i]].x,l[rez[i]].y);

}