#include <iostream>
#include <stdio.h>
#include <vector>

#define Nmax 400010

using namespace std;

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

struct rez{
    int x, y;
} apm[10000];

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 rangul(int x)
{
    if(g[x] == x) return x;
    g[x] = rangul(g[x]);
    return g[x];
}

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

}
bool cmpf(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, cmpf );

    int t=-1;
    for(int i=1;i<=m;i++)


        if(rangul(x[ind[i]]) != rangul(y[ind[i]]))
            s += c[ind[i]],
            uneste(x[ind[i]],y[ind[i]]),
            apm[++t].x = x[ind[i]],
            apm[t].y = y[ind[i]];

    cout << s << "\n";
    cout << t+1 << "\n";

    for(int i=0;i<=t;i++)
        cout<<apm[i].x<<" "<<apm[i].y<<"\n";


    return 0;
}