#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 200001
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct muchie
{
    int x,y,c;
} v[NMAX], sol[NMAX];
bool cmp(muchie a, muchie b)
{
    if(a.c < b.c)
        return true;
    return false;
}
int i, n, ap[NMAX], c1, c2, j, k, m, ct=0;
int main()
{
    in>>n>>m;
    for(i=1;i<=m;i++)
        in>>v[i].x>>v[i].y>>v[i].c;

    sort(v+1,v+m+1,cmp);
//    for(i=1;i<=m;i++)
//        cout<<v[i].x<<' '<<v[i].y<<' '<<v[i].c<<'\n';
//    cout<<'\n';
    //kruskal
    for(i=1; i<=n; i++)
        ap[i] = i;
    ct = 0;
    k=0; i = 1;
    while(k < n-1)
    {
        if(ap[v[i].x] != ap[v[i].y])
        {
            k++;
            sol[k] = v[i];
            ct += v[i].c;
            //unificam comp. conexe
            c1 = ap[v[i].x];
            c2 = ap[v[i].y];
            for(j=1; j<=n; j++)
                if (ap[j] == c2) ap[j] = c1;
        }
        i++;
    }
    out<<ct<<'\n'<<k<<'\n';
    for(i=1;i<=k;i++)
        out<<sol[i].y<<' '<<sol[i].x<<'\n';

    return 0;
}