#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 200001
#define MAXE 400001
struct muchie{int x,y,c;}E[MAXE];
int F[MAXN],M[MAXN],cost,n,m;
int comp(muchie a, muchie b)
{
    return a.c < b.c;
}
int find(int nod)
{
    int R=nod,aux;
    for(;F[R]!=0;R=F[R]);
    for(;nod!=R;aux=F[nod],F[nod]=R,nod=aux);
    return R;
}
bool APM(int X, int Y)
{
    int a=find(X),b=find(Y);
    if(a!=b)
        F[a]=b;
    return (a!=b);
}
void kru()
{
    int i;
    sort(E+1,E+m+1,comp);
    for(i=1;i<=m;i++)
        if(APM(E[i].x,E[i].y))
        {
            M[++M[0]]=i;
            cost+=E[i].c;
        }
}
int main()
{
    int i;
    freopen("apm.in","r",stdin);
    scanf("%d %d\n",&n,&m);
    for(i=1;i<=m;i++)
        scanf("%d %d %d\n",&E[i].x,&E[i].y,&E[i].c);
    fclose(stdin);
    kru();
    freopen("apm.out","w",stdout);
    printf("%d\n%d\n",cost,n-1);
    for(i=1;i<=M[0];i++)
        printf("%d %d\n",E[M[i]].x,E[M[i]].y);
    fclose(stdout);
    return 0;
}