#include <iostream>
#include <fstream>
#include <math.h>
#include <utility>
#include <algorithm>
#define nmax 200000
#define mmax 400000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,l[nmax+5];
pair<int,int> gg[nmax+5];
struct muchie
{
  int nod1,nod2,info;
}v[mmax+5],apm[nmax+5];
void Insertion_Sort(muchie arr[],int n)
{
    int i,j;
    muchie key;
    for(i=2;i<=n;i++)
    {
        key=arr[i];
        j=i-1;
        while(j>0 && arr[j].info>key.info)
        {
            arr[j+1]=arr[j];
            j--;

        }
            arr[j+1]=key;
    }
}
void merge_Sort(muchie arr[],int l,int m, int r)
{
    muchie R[(nmax+5)/2],L[(nmax+5)/2];
    for(int Ri=1,i=l;i<=m;i++,Ri++)
        R[Ri]=arr[i];
    for(int Li=1,i=m+1;i<=r;Li++,i++)
        L[Li]=arr[i];
    int i=0,j=0,k=l;
    int n1 = m - l + 1;
    int n2 =  r - m;
     while (i < n1 && j < n2)
    {
        if (L[i].info <= R[j].info)
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }

}
void Merge_Sort(muchie arr[],int l, int r)
{
    if(l<r)
    {
        int m=l+(r-l)/2;
        Merge_Sort(arr,l,m);
        Merge_Sort(arr,m+1,r);
        merge_Sort(arr,l,m,r);
    }
}
void Quick_Sort(muchie arr[],int l,int r)
{
    int i=l,j=r;
    muchie tmp;
    int pivot=arr[l+(r-l)/2].info;
    while(i<=j)
    {
        while(arr[i].info<pivot)
            i++;
        while(arr[j].info>pivot)
            j--;
        if(i<=j)
        {
            tmp=arr[i];
            arr[i]=arr[j];
            arr[j]=tmp;
            i++;
            j--;
        }
    }
    if (l < j)
            Quick_Sort(arr, l, j);
      if (i < r)
            Quick_Sort(arr, i, r);
}
void Intro_Sort(muchie arr[],int n)
{
    if(n<=16)
        Insertion_Sort(arr,n);
    else if(log(n)==0)
        Merge_Sort(arr,1,n);
    else
        Quick_Sort(arr,1,n);

}
int main()
{
    fin>>n>>m;
    int x,y,z,k=0,ct=0,a,b,ggi=1;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        v[i].nod1=x;
        v[i].nod2=y;
        v[i].info=z;
    }
    Intro_Sort(v,m);
    for(int i=1;i<=n;i++)
        l[i]=i;
    int i=1;
    while(k<n-1)
    {
        if(l[v[i].nod1]!=l[v[i].nod2])
        {
            a=l[v[i].nod2];
            b=l[v[i].nod1];
            ct+=v[i].info;
            k++;
            gg[ggi]=make_pair(v[i].nod1,v[i].nod2);
            ggi++;
            for(int j=1;j<=n;j++)
                if(l[j]==b)
                l[j]=a;
        }
        i++;
    }
    fout<<ct<<"\n"<<ggi-1<<"\n";
    for(int i=1;i<ggi;i++)
        if(i==ggi-1)
            fout<<gg[i].second<<" "<<gg[i].first;
        else
            fout<<gg[i].second<<" "<<gg[i].first<<"\n";
    fin.close();
    fout.close();
    return 0;
}