#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define MMAX 400003
#define NMAX 200002

using namespace std;

ifstream fi("apm.in");
ofstream fo("apm.out");

int n,m;
pair<int,pair<int,int>> mch[MMAX];
vector <pair<int,int>> rasp;
int rang[NMAX], tata[NMAX], total;

void citire()
{
    fi >> n >> m;
    for(int i = 1; i <= m; ++i)
        fi >> mch[i].second.first >> mch[i].second.second >> mch[i].first;
}

void uneste(int nod1, int nod2)
{
    if(rang[nod1] > rang[nod2])
        tata[nod2] = nod1;
    else
        tata[nod1] = nod2;
    if(rang[nod1] == rang[nod2])
        ++ rang[nod2];
}

int da_grupa(int nod)
{
    int nod_tata = nod;
    while(nod_tata != tata[nod_tata])
        nod_tata = tata[nod_tata];

    while(nod != tata[nod])
    {
        int aux = tata[nod];
        tata[nod] = nod_tata;
        nod = aux;
    }
    return nod_tata;
}

void init()
{
    for(int i = 1; i <= m; ++i)
    {
        tata[i] = i;
        rang[i] = 1;
    }
}

void kruskal()
{
    init();
    sort(mch+1,mch+m+1);
    int grupa1, grupa2, cost;
    for(int i = 1; i <= m; ++i)
    {
        grupa1 = da_grupa(mch[i].second.first);
        grupa2 = da_grupa(mch[i].second.second);
        if(grupa1 != grupa2)
        {
            uneste(grupa1, grupa2);
            total += mch[i].first;
            rasp.push_back({mch[i].second.first,mch[i].second.second});
            //if(rasp.size() == n - 1)
              //  break;
        }
    }
}

void afish()
{
    fo << total << '\n' << rasp.size() << '\n';
    for(auto i : rasp)
        fo << i.first << ' ' << i.second << '\n';
}

int main()
{
    citire();
    kruskal();
    afish();
    return 0;
}