#include <fstream>
#include <iostream>
#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 ind[400010];
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 int &x, const int &y)
{
    if(a[x].c>a[y].c) return 0;
    else return 1;
}


int main()
{

    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d %d", &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;
        scanf("%d", &a[i].x);
        scanf("%d", &a[i].y);
        scanf("%d", &a[i].c);

        ind[i]=i;

    }

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

    i=1;

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

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

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

    printf("%d\n%d\n", ct,n-1);
    for(i=1; i<=n-1; i++) //fout<<sol2[i]<<" "<<sol1[i]<<'\n';
        printf("%d %d\n", sol2[i], sol1[i]);

    return 0;
}