#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct elem
{
    int x,y,c;
}v[400005],mem[400005];
int n,m;
bool comp(elem a, elem b)
{
    return a.c<b.c;
}
void kruskal(int n,int m,elem v[])
{
    int i,j,k,L[200005],nr1,nr2,cnt=0;
    long long ct=0;
     for(i=1;i<=n;i++)
        L[i]=i;
     k=1;i=1;
     while(k<=n-1)
     {
         if(L[v[i].x]!=L[v[i].y])
         {
             k++;
             cnt++;
             mem[cnt].x=v[i].y;
             mem[cnt].y=v[i].x;
             ct+=v[i].c;
             nr1=L[v[i].x];
             nr2=L[v[i].y];

             for(j=1;j<=n;j++)
                if(L[j]==nr2)
                L[j]=nr1;
         }
         i++;
     }
     g<<ct<<endl<<k-1<<endl;
     for(int i=1;i<k;i++)
        g<<mem[i].x<<" "<<mem[i].y<<'\n';
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1, v+m+1, comp);
   kruskal(n,m,v);

    return 0;
}