#include <iostream>
#include <stdio.h>
#define NMAX 400001
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",&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];
}
int uneste(int x,int y)
{
        g[ra(x)]=ra(y);
}
bool comp(int i,int j)
{
    return (c[i]<c[j]);
}
int main()
{
    citire();
    for (int i=1;i<=n;i++)
        g[i]=i;
    int t=-1;
    sort(ind+1,ind+1+m,comp);
    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]];
        }
    freopen ("apm.out","w",stdout);
    printf ("%d\n%d\n",s,t+1);
    for (int i=0;i<=t;i++)
        printf("%d %d\n",a[i].y,a[i].x);
    return 0;
}