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

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

struct muchie
{
    int x,y,cost;
}v[200100];

int compare (muchie A, muchie B)
{
    return (A.cost<B.cost);
}

struct
{
    int X,Y;
}sol[200100];

int n;
void kruskal ()
{
    int i,j,l[200100],ct,k,a,b;
    for(i=1;i<=n;i++)l[i]=i;
    ct=0;
    k=0;
    i=1;

    while(k<n-1)
    {
     a=l[v[i].x];
     b=l[v[i].y];

     if(a!=b)
     {
         k++;
         ct+=v[i].cost;
         sol[k].X=v[i].x;
         sol[k].Y=v[i].y;
         for(j=1;j<=n;j++)if(l[j]==a)l[j]=b;
     }
    i++;
    }
    g<<ct<<'\n';
    g<<n-1<<'\n';
    for(i=1;i<=k;i++)
        g<<sol[i].X<<" "<<sol[i].Y<<'\n';
}

int i,m;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>v[i].x>>v[i].y>>v[i].cost;
    }
    sort(v+1,v+m+1,compare);


    kruskal();
    return 0;
}