#include <iostream>
#include <fstream>

using namespace std;

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


struct Nod
{

    int x,y,c;

} v[400001],sch,v1[400001];

int main()
{

    int n,m,i,j,l[200001],ct,k,nr1,nr2,aux,idx=0;
    f >> n >> m;
    for(i=0; i<m; i++)
    {
        f >> v[i].x >> v[i].y >> v[i].c;
    }

    for(i=0; i<m-1; i++)
    {
        for(j=i+1; j<m; j++)
        {
            if(v[i].c>v[j].c)
            {
                sch=v[i];
                v[i]=v[j];
                v[j]=sch;
            }
        }
    }

    for(int i=1; i<=n; i++)
        l[i]=i;

    k=0;
    ct=0;
    aux=0;

    while(k<n-1)
    {

        if(l[v[aux].x]!=l[v[aux].y])
        {
            k++;
            v1[idx]=v[aux];
           idx=idx+1;
            ct=ct+v[aux].c;
            nr1=l[v[aux].x];
            nr2=l[v[aux].y];
            for(j=1; j<=n; j++)
                if(l[j]==nr2)
                    l[j]=nr1;

        }
        aux++;


    }
    g<<ct<<endl;
    g<<idx<<endl;
    for(i=0;i<idx;i++)
        g<<v1[i].x<<" "<<v1[i].y<<endl;






    return 0;
}