#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 200005

using namespace std;

int n,m,cost_minim,poz;

pair<int,int> de_afisat[N];

struct muchii
{
    int x,y,cost;
} vec[N];

int adancime[N],tata[N];

void initializare()
{
    for(int i = 1 ; i <= n ; ++i)
    {
        tata[i] = i;
    }
}

int comp(muchii a, muchii b)
{
    return(a.cost < b.cost);
}

int radacina(int x)
{
    int x1 = x;
    while(tata[x] != x)
    {
        x = tata[x];
    }

    int tmp;
    while(tata[x1] != x1)
    {
        tmp = x1;
        x1 = tata[x1];
        tata[tmp] = x;
    }
    return x;
}

void join(int x, int y, int rad1, int rad2)
{
    if(adancime[x] == adancime[y])
    {
        tata[rad2] = rad1;
        adancime[rad2]++;
        return;
    }

    if(adancime[x] < adancime[y])
    {
        tata[rad1] = rad2;
    }
    else
    {
        tata[rad2] = rad1;
    }
}

void afisare()
{
    for(int i = 0 ; i < poz ; ++i)
    {
        printf("%d %d\n",de_afisat[i].first, de_afisat[i].second);
    }
}

void prelucrare()
{
    sort(vec,vec + n,comp);

    int tmp1,tmp2;

    for(int i = 0 ; i < m ; ++i)
    {
        tmp1 = radacina(vec[i].x);
        tmp2 = radacina(vec[i].y);

        if(tmp1 != tmp2)
        {
            cost_minim += vec[i].cost;
            join(vec[i].x,vec[i].y,tmp1,tmp2);

            de_afisat[poz++] = make_pair(vec[i].x , vec[i].y);
        }
    }
}

void citire()
{
    scanf("%d %d\n",&n,&m);

    initializare();

    for(int i = 0 ; i < m ; ++i)
    {
        scanf("%d %d %d\n",&vec[i].x,&vec[i].y,&vec[i].cost);
    }

    prelucrare();
}

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

    citire();

    printf("%d\n%d\n",cost_minim,n-1);

    afisare();

    return 0;
}