#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int nmax = 100005;
int n, m, T[nmax], rang[nmax], cost;
vector< pair< int, pair<int, int> > > E, sol;

int multime(int nod)
{
    if(T[nod] != nod)
        T[nod] = multime(T[nod]);

    return T[nod];
}

void reuniune(int i, int j)
{
    i = multime(i);
    j = multime(j);

    if(i == j)
        return ;

    if(rang[i] < rang[j])
        T[i] = j;
    else
        T[j] = i;

    if(rang[i] == rang[j])
        rang[i] ++;
}

void Kruskal()
{
    for(auto i : E)
    {
        int x = multime(i.second.first);
        int y = multime(i.second.second);

        if(x != y){
            reuniune(x, y);
            sol.push_back(i);
            cost += i.first;
        }
    }
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= n; i ++)
        T[i] = i;

    for(int i = 1; i <= m; i ++)
    {
        int c, x, y;
        f >> x >> y >> c;

        E.push_back({c, {x, y}});
    }

    sort(E.begin(), E.end());

    Kruskal();

    g << cost << '\n' << sol.size() << '\n';
    for(auto i : sol)
        g << i.second.first << " " << i.second.second << '\n';
    return 0;
}