#include <bits/stdc++.h>
#define nmax 200005
using namespace std;

int n,m1;
int x[nmax],y[nmax],c[nmax],ind[nmax];
int gr[nmax];
stack<int> s;

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

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


int main()
{
    int i,sol=0;
    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( group( x[ind[i]] ) != group ( y[ ind[i] ] ))
        {
            gr[ group( x[ ind[i] ] ) ]=group( y[ind[i]]);
            sol+=c[ind[i]];
           s.push( ind[i]);
        }
    }
    printf("%d\n%d\n",sol,s.size());
    while(!s.empty())
    {
        printf("%d %d\n",x[ s.top() ],y[s.top()]);
        s.pop();
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}