#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    long x,y,z;
}e[200007];
long n,m,t[200007],cost,sol[3][200007],kk;
void citire()
{
    f>>n>>m;
    for(long k=0;k<m;k++)f>>e[k].x>>e[k].y>>e[k].z;
}
void reuneste(int i,int j)
{
    int k; i=t[i]; j=t[j];
    if(i==j)return;
    for(k=1;k<=n;k++)
        if(t[k]==i)t[k]=j;
}
int compp(const void *a,const void *b)
{
    return ((int*) a)[2]-((int*) b)[2];
}
void kruskal(void)
{
    int i,j,k,c;
    qsort(e,m,sizeof(e[0]),compp);
    for(i=1;i<=n;i++)t[i]=i;
    for(k=0;k<m;k++)
    {
        i=e[k].x; j = e[k].y;
        c=e[k].z;
        if(t[i]==t[j])continue;
        reuneste(i,j);
        cost+=c;
        sol[1][kk]=i; sol[2][kk]=j; kk++;
    }
}
int main()
{
    citire();
    kruskal();
    g<<cost<<'\n'<<n-1<<'\n';
    for(long i=0;i<kk;i++)g<<sol[1][i]<<" "<<sol[2][i]<<'\n';
    f.close();  g.close();
    return 0;
}