#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct muchie
{
    int i,j,cost;
};
struct nou
{
    int no1, no2;
};
nou v[1500];
int n, m, t[101];
muchie x[5000];
bool sorta (muchie a, muchie b)
{
    if(a.cost<b.cost)
        return 1;
    else if(a.cost==b.cost)
    {
        if(a.i<b.i)
            return 1;
        return 0;
    }
    else
        return 0;
}
int main()
{
    in>>n>>m;
    for(int ind=0; ind<m; ++ind)
        in>>x[ind].i>>x[ind].j>>x[ind].cost;
    //sortez in functie de cost
    sort(x, x+m, sorta);
    //initializare reprezentanti
    for(int ind=1; ind<=n; ++ind)
        t[ind]=ind;
    //apm
    int s=0, cnt=0, cate=0;
    for(int ind=0; ind<m; ++ind)
    {
        if(t[x[ind].i] != t[x[ind].j])
        {
            s += x[ind].cost;
            ++cnt;
            v[cate].no1 = x[ind].j;
            v[cate].no2 = x[ind].i;
            ++cate;
          //  cout<<x[ind].j<<" "<<x[ind].i<<'\n';
            //reunim subarbori
            int arb_i = t[x[ind].i], arb_j=t[x[ind].j];
            for(int k=1; k<=n; ++k)
            {
                if(t[k]==arb_j)
                {
                    t[k]=arb_i;
                    
                }
            }
        }
        
    }
    out<<s<<'\n'<<cnt<<'\n';
    //afisare muchii
    for(int ind=0; ind<cate; ++ind)
        out<<v[ind].no1<<" "<<v[ind].no2<<'\n';
    return 0;
}