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

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

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

int reuniune(int n1,int n2)
{
    gr[n1]=gr[n2];
}

int cmp(int a,int b)
{
    return c[a]<c[b];
}

int main()
{
    int i,n1,n2,co;
    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<=n;i++) gr[i]=i;
    sort(ind+1,ind+m1+1,cmp);

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

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