#include <iostream>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m;
struct muchie
{
    int x,y,cost;
}v[400003],aux;
int M[200003];
bool inc[400002];
int v1[200003];
int aux1,aux2;
int quicksort(int st,int dr)
{
    int i=st;
    int j=dr;
    int x=v[i+(j-i)/2].cost;
    while(i<=j)
    {
        while(i<dr && v[i].cost<x)
            i++;
        while(j>st&& v[j].cost>x)
            j--;
        if(i<=j)
        {
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
            ++i;
            j--;
        }
    }
    if(st<j)
        quicksort(st,j);
    if(i<dr)
        quicksort(i,dr);
}
int kruscal()
{
    int i,j;
    for(i=1;i<=n;i++)
        M[i]=i;
    int nr=0;
    int s=0;
    i=1;
    while(nr<n-1)
    {
        v1[v[i].x]++;
        v1[v[i].y]++;
        if(M[v[i].x]!=M[v[i].y])
        {
            nr++;
            s+=v[i].cost;
            inc[i]=true;
            aux1=M[v[i].x];
            aux2=M[v[i].y];
            if(v1[v[i].x]==1&&v1[v[i].y]==1)
            {
                if(aux1<aux2)
                    M[v[i].y]=aux1;
                else
                    M[v[i].x]=aux2;
            }
            else
            {
                if(aux1<aux2)
                {
                    for(j=1;j<=n;j++)
                        if(M[j]==aux2)
                        {
                            M[j]=aux1;
                        }
                }
                else
                {
                    for(j=1;j<=n;j++)
                        if(M[j]==aux1)
                        {
                            M[j]=aux2;
                        }
                }
            }
        }
        i++;
    }
    return s;
}
int main()
{
    f>>n>>m;
    int i;
    for(i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].cost;
    quicksort(1,m);
   // for(i=1;i<=m;i++)
    //    g<<v[i].x<<" "<<v[i].y<<" "<<v[i].cost<<"\n";
    int s=kruscal();
    g<<s<<"\n"<<n-1<<"\n";
    for(i=1;i<=m;i++)
        if(inc[i]==true)
            g<<v[i].x<<" "<<v[i].y<<"\n";
    return 0;
}