#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 200002
#define MMAX 400002

using namespace std;

ifstream f("apm.in");
ofstream o("apm.out");

int n,m;
pair <int,pair<int,int>> vm[MMAX];
int rang[NMAX], tata[NMAX];
vector <pair<int,int>> ras;
int cfinal;

void input()
{
    f >> n >> m;
    for(int i = 1; i <= m; ++i)
        f >> vm[i].second.first >> vm[i].second.second >> vm[i].first ;
}

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

int da_grp(int nod)
{
    int aux1 = nod, aux;
    while(aux1 != tata[aux1])
        aux1 = tata[aux1];
    while(nod != tata[nod])
    {
        aux = tata[nod];
        tata[nod] = aux1;
        nod = aux;
    }
    return aux1;
}

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] ++;
}

void kruskal()
{
    init_pdr();
    sort(vm+1,vm+m+1);

    int nod1,nod2,cost;
    for(int i = 1; i <= m; ++i)
    {
        nod1 = vm[i].second.first;
        nod2 = vm[i].second.second;
        cost = vm[i].first;

        if(da_grp(nod1) == da_grp(nod2))
            continue;
        uneste(da_grp(nod1),da_grp(nod2));
        ras.push_back({nod1,nod2});
        cfinal += cost;
    }
}

void output()
{
    o << cfinal << '\n' << n - 1 << '\n';
    for(const auto& i: ras)
        o << i.first << ' ' << i.second << '\n';
}

int main()
{
    input();
    kruskal();
    output();
    return 0;
}