#include <iostream>
#include <fstream>
#define nmax 400001
#define inf 0x3f3f3f

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,u,v,nr=0,ct=0,z[nmax];
struct muchie
{
    int x,y,cost,ok;
}c[nmax];
int main()
{
    fin>>n>>m;
    for(int i =1 ; i <= m ; i ++)
    {
            fin>>c[i].x>>c[i].y>>c[i].cost;
    }
    for(int i =1 ; i <= n ; i++)
        z[i]=i;
    for(int i =1 ; i < m ; i++)
    {
        for(int j =i+1 ; j <=m ; j ++)
            if(c[i].cost>c[j].cost)
        {
            muchie aux;
            aux=c[i];
            c[i]=c[j];
            c[j]=aux;
        }
    }

    int i=1;

    while(nr<n-1)
    {
        u=z[c[i].x];
        v=z[c[i].y];
        if(u!=v)
        {
            nr++;
            ct=ct+c[i].cost;
             c[i].ok=1;
             for(int j =1 ; j <= n ; j++)
                if(z[j]==v)
                 z[j]=u;
        }
        i++;
    }
    fout<<ct<<'\n';
    fout<<nr<<'\n';
    for(int i =1 ; i <= m ; i++)
        if(c[i].ok) fout<<c[i].x<<" "<<c[i].y<<'\n';


    return 0;
}