#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[400010];

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;
    else
        return ra(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]]),
            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;
}