#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int nr, cost_total, n, m, depth[200003], T[200003];

struct muchie{
    int plecare, destinatie, cost;
}graf[400005];
queue <muchie> sol_muchii;
muchie var;

bool cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

void initial()
{
    int i;
    for(i = 1; i <= n; i++)
        T[i] = i, depth[i] = 1;
}

int radacina(int k)
{
    while(T[k] != k)
        k = T[k];
    return k;
}

void unire(int a, int b)
{
    if(depth[a] > depth[b])
        T[b] = a;
    else
    {
        T[a] = b;
        if(depth[a] == depth[b])
            depth[b]+=1;
    }
}

int main()
{
    int i, a, b;
    fin >> n >> m;
    for(i = 0; i < m; i++)
        fin >> graf[i].plecare >> graf[i].destinatie >> graf[i].cost;
    sort(graf, graf + m, cmp);
    initial();
    for(i = 0; i < m; i++)
    {
        a = graf[i].plecare, b = graf[i].destinatie;
        a = radacina(a), b = radacina(b);
        if(a != b)
            nr++, sol_muchii.push(graf[i]), unire(a, b), cost_total+= graf[i].cost;
    }
    fout << cost_total << '\n' << nr << '\n';
    while(!sol_muchii.empty())
    {
        var = sol_muchii.front();
        sol_muchii.pop();
        fout << var.destinatie << ' ' << var.plecare << '\n';
    }
    return 0;
}