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

using namespace std;

const int maxn = 400100;

int gr[maxn],x[maxn],y[maxn],c[maxn],n,m,indice[maxn],cost;
vector<int> v;

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

    for(int i=1;i<=n;++i)
        gr[i]=i; //MakeSet(v)
}

int grupa(int i) //FindSet
{
    if (gr[i] == i)
        return i;
    gr[i] = grupa(gr[i]);
    return gr[i];
}

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

void reuniune(int i,int j)
{
    gr[grupa(i)] = grupa(j);
}

int main()
{
    citire();
    sort(indice+1,indice+m+1,cmp);

    for(int i=1;i<=m;++i)
    {
        if (grupa(x[indice[i]]) != grupa(y[indice[i]]))
        {
            cost+=c[indice[i]];
            reuniune(x[indice[i]],y[indice[i]]);
            v.push_back(indice[i]);
        }
    }

    printf("%d\n",cost);
    printf("%d\n",n-1);
    for(int i=0;i<n-1;++i)
        printf("%d %d\n",x[v[i]],y[v[i]]);

    return 0;
}