#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie
{

    int x,y,c;

} a[400010];

int tata[200010],sol1[200010],sol2[200010];
int aux[20010];
int i,j,n,m,ct,k,v,w;

int radacina (int a)
{
    int r=a;
    while(tata[r]!=r)
    {
        r=tata[r];
    }

    while(tata[a]!=a)
    {
        int aux=tata[a];
        tata[a]=r;
        a=aux;
    }

    return r;
}
bool cmp(const muchie &a, const muchie &b)
{
    if(a.c>b.c) return 0;
    else return 1;
}


int main()
{
    fin>>n>>m;

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

    for(i=1; i<=m; i++)
    {
        fin>>a[i].x>>a[i].y>>a[i].c;


    }

    sort(a+1,a+m+1,cmp);



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

        if(v!=w)
        {
            k++;
            ct+=a[i].c;
            sol1[k]=a[i].x;
            sol2[k]=a[i].y;
            tata[v]=w;

        }
        i++;
    }

    fout<<ct<<'\n'<<n-1<<'\n';

    for(i=1; i<=n-1; i++) fout<<sol2[i]<<" "<<sol1[i]<<'\n';

    return 0;
}