#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n,m,i,x[200002],y[200002],c[200002],ct,k,v[200002];
int gr[200002],ind[200002];

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

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

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

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x[i]>>y[i]>>c[i];
        ind[i]=i;
    }

    sort(ind+1,ind+m+1,cmp);

    for(i=1;i<=n;i++)
    {
        gr[i]=i;
    }
    ct=0;
    for(i=1;i<=m;i++)
    {
        if(grupa(x[ind[i]]) != grupa(y[ind[i]]))
        {
            ct += c[ind[i]];
            reuniune(x[ind[i]],y[ind[i]]);
            v[++k]=ind[i];
        }
    }

    fout<<ct<<"\n"<<n-1<<"\n";

    for(i=1;i<=k;i++)
    {
        fout<<x[v[i]]<<" "<<y[v[i]]<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}