//Arborele partial de cost minim utilizand algoritmul lui Kruskal
//implementat cu ajutorul multimilor disjuncte si cu heap
#include <cstdio>
#define N 100010
#define M 400010
#define reuneste(a,b) uneste(gaseste(a),gaseste(b))

int A[M][3],P[N],C[M],rang[N],st[M][3],total,kont,n,m,i;

int gaseste(int x)
{
    if (x!=P[x]) P[x]=gaseste(P[x]);
    return P[x];
}

void uneste(int x, int y)
{
    if (rang[x]<rang[y]) P[x]=y;
    else
    {
        P[y]=x;
        if (rang[x]==rang[y]) rang[x]++;
    }
}

void down(int tata, int m)
{
    int t,i,fiu=tata<<1;
    if (fiu<m && C[fiu|1]<C[fiu]) fiu|=1;
    while (fiu<=m && C[tata]>C[fiu])
    {
        for (i=1; i<=2; i++)
        {
            t=A[tata][i]; A[tata][i]=A[fiu][i]; A[fiu][i]=t;
        }
        t=C[tata]; C[tata]=C[fiu]; C[fiu]=t;
        tata=fiu; fiu<<=1;
        if (fiu<m && C[fiu|1]<C[fiu]) fiu|=1;
    }
}

void build_heap()
{
    for (int i=m>>1; i; i--) down(i,m);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for (i=1; i<=m; i++) scanf("%d %d %d\n",&A[i][1],&A[i][2],&C[i]);
    build_heap();
    for (i=1; i<=n; i++)
    {
        P[i]=i;
        rang[i]=0;
    }
    total=0;
    kont=0;
    //algoritmul lui Kruskal
    while (kont<n-1)
    {
        if (gaseste(A[1][1])!=gaseste(A[1][2]))
        {
            reuneste(A[1][1],A[1][2]);
            total+=C[1];
            kont++;
            st[kont][1]=A[1][1]; st[kont][2]=A[1][2];
        }
        A[1][1]=A[m][1]; A[1][2]=A[m][2];
        C[1]=C[m];
        down(1,--m);
    }
    printf("%d\n%d\n",total,kont);
    for (i=1; i<=kont; i++) printf("%d %d\n",st[i][1],st[i][2]);

    return 0;
}