#include <iostream>
#include <fstream>
using namespace std;

struct muchie
{
    int x,y,c;
}G[100001],sol[100001];

int i,n,m,C[100001],j,k,ct,n1,n2;

ifstream f("apm.in");
ofstream g("apm.out");

int main()
{
    f >> n >> m;
    for(i=1;i<=m;i++)
        f>>G[i].x>>G[i].y>>G[i].c;
    //initializez - consider ca fiecare varf al grafului face parte dintr-o comp. conexa
    for(i=1;i<=n;i++)
        C[i] = i;
    ///sortam crescator dupa cost muchiile
    for(i=1;i<m; i++)
        for(j=i+1; j<=m; j++)
        if (G[i].c> G[j].c){
            swap(G[i], G[j]);
        }

    ///Kruskal
    k=0;
    i=1;
    ct = 0;
    while(k<n-1){
        if (C[G[i].x] != C[G[i].y]){
            k++;
            ct += G[i].c;
            sol[k]=G[i];
            ///unificam comp. conexe a celor 2 varfuri
            n1=C[G[i].x];
            n2=C[G[i].y];
            for(j=1;j<=n;j++)
                if (C[j] == n2) C[j] = n1;
        }
        i++;
    }
    g<<ct << endl;
    g<<k<<endl;
    for(i=1;i<=k;i++)
        g << sol[i].y << " " << sol[i].x <<  endl;
    return 0;
}