#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define nmax 400010
using namespace std;

int x[nmax],y[nmax],c[nmax],ind[nmax];
int gr[nmax];
int n,m1,sol;
vector<int> so;

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

int grup(int nod)
{
    if(gr[nod]==nod) return nod;
    gr[nod]=grup(gr[nod]);
    return gr[nod];
}

int unite(int a,int b)
{
    gr[b]=a;
}

int main()
{
    int i;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m1);
    for(i=1;i<=m1;i++)
    {
        scanf("%d%d%d",&x[i],&y[i],&c[i]);
        ind[i]=i;
    }

    for(i=1;i<=m1;i++) gr[i]=i;
    sort(ind+1,ind+m1+1,comp);

    for(i=1;i<=m1;i++)
        if( grup( x[ ind[i] ] )!=grup( y[ ind[i]] ) )
        {
            sol+=c[ ind[i] ];
            unite( grup( x[ind[i]]) , grup(y[ind[i]] ) );
            so.push_back(ind[i]);
        }

    printf("%d\n%d\n",sol,so.size());
    for(i=0;i<so.size();i++)
        printf("%d %d\n",x[so[i]],y[so[i]]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}