//#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
int n,m,s,mn,arb[200005],i,p,arbc,k,j,a[400005],b[400005],ast,adr,conect[200005];

ifstream cin("apm.in");
ofstream cout("apm.out");

struct muchii
{
    int x,y,c;
} u[400005];

bool fcomp (muchii a, muchii b)
{
    return (a.c<b.c);
}
int cauta(int x)
{
    int radacina, y;


    radacina = x;
    while(conect[radacina] != radacina) radacina = conect[radacina];

    while(conect[x] != x)
    {
        y = conect[x];
        conect[x] = radacina;
        x = y;
    }
    return radacina;
}

void uneste(int x, int y)
{

    if (arb[x] > arb[y]) conect[y] = x;
    else conect[x] = y;

    if (arb[x] == arb[y]) arb[y]++;
}

int main()
{int cauta_ast,cauta_adr;
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>u[i].x>>u[i].y>>u[i].c;
    }
    sort(u+1,u+m+1,fcomp);
    for(i=1; i<=n; i++)
    {
        arb[i]=0;
        conect[i]=i;

    }
    s=0;
    k=0;
    for(i=1; i<=m ; i++)
    {
        //if(arb[u[i].x]!=arb[u[i].y])
       // {
        ast=u[i].x;
        adr=u[i].y;
        cauta_ast=cauta(ast);
        cauta_adr=cauta(adr);
        if(cauta_ast!=cauta_adr)
        {
            s=s+u[i].c;
            k++;
            a[k]=u[i].x;
            b[k]=u[i].y;
            uneste(cauta_ast, cauta_adr);
        }
        /*for(j=1;j<=n;j++)
        {
            if(arb[j]==adr)
                arb[j]=ast;
        }*/
    }

  //  cout<"*****";
    cout<<s<<'\n'<<n-1<<'\n';
    for(i=1; i<=n-1; i++)
        cout<<a[i]<<" "<<b[i]<<'\n';
    return 0;
}