#include <algorithm>
#include <cstdio>

using namespace std;

const int N=200005, M=400005;

struct muchii
{
    int x, y, c;
    bool operator <(const muchii &e) const
    {
        return c<e.c;
    }
};

muchii A[M];
int f[N], sol[M];

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int n, m, i, x, y, aux, r1, r2, s=0;
    scanf("%d%d", &n, &m);
    for(i=1;i<=m;i++) scanf("%d%d%d", &A[i].x, &A[i].y, &A[i].c);
    sort(A+1, A+m+1);
    for(i=1;i<=n;i++) f[i]=i;
    for(i=1;i<=m;i++)
    {
        for(x=A[i].x;f[x]!=x;x=f[x]);
        for(y=A[i].x;y!=x;y=aux)
        {
            aux=f[y];
            f[y]=x;
        }
        r1=x;
        for(x=A[i].y;f[x]!=x;x=f[x]);
        for(y=A[i].y;y!=x;y=aux)
        {
            aux=f[y];
            f[y]=x;
        }
        r2=x;
        if(r2!=r1)
        {
            s+=A[i].c;
            sol[++sol[0]]=i;
            f[f[A[i].x]]=f[A[i].y];
        }
    }
    printf("%d\n%d\n", s, n-1);
    for(i=1;i<n;i++) printf("%d %d\n", A[sol[i]].x, A[sol[i]].y);
}