#include <iostream>
#include <stdio.h>
#define Nmax 400010

using namespace std;

int x[Nmax], y[Nmax], c[Nmax], ind[Nmax], g[Nmax],n , m, s;

struct r{
    int x, y;
} a[Nmax];

void citire()
{
    freopen("apm.in","r",stdin);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d\n",&x[i],&y[i],&c[i]);
        ind[i]=i;
    }
}

int ra(int x)
{
    if(g[x] == x)
        return x;
    g[x] = ra(g[x]);
    return g[x];
}

void uneste(int x,int y)
{
    g[ra(x)] = ra(y);
}

bool comp(int i,int j)
{
    return(c[i] < c[j]);
}

int main()
{
    freopen("apm.out","w",stdout);
    citire();
    for(int i=1;i<=n;i++)
        g[i] = i;
    sort( ind+1, ind+1+m, comp );
    int t=-1;
    for(int i=1;i<=m;i++)
        if(ra(x[ind[i]]) != ra(y[ind[i]]))
            s += c[ind[i]],
            uneste(x[ind[i]],y[ind[i]]),
            a[++t].x = x[ind[i]],
            a[t].y = y[ind[i]];
    printf("%d\n%d\n",s,t+1);
    for(int i=0;i<=t;i++)
        printf("%d %d\n",a[i].x,a[i].y);
    return 0;
}