#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

struct muchie
{
    int i;
    int j;
    int cost;
};
muchie m[400001];
int sef[200001];

int boss(int x)
{
    if(sef[x] == x)
    {
        return x;
    }
    else
    {
        return sef[x] = boss(sef[x]);
    }
}

void unire(int x, int y)
{
    int sef_x = boss(x);
    int sef_y = boss(y);

    sef[sef_y] = sef_x;
}

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

    int N, M;
    f >> N >> M;
    for(int i = 1; i <= N; i++)
    {
        sef[i] = i;
    }
    for(int k = 1; k <= M; k++)
    {
        f >> m[k].i >> m[k].j >> m[k].cost;
    }
    sort(m + 1, m + M + 1, [](muchie &a, muchie &b) {return a.cost < b.cost; }); // aparent asa pt sort muchie in functie de cost

    int S = 0;
    for(int k = 1; k <= M; k++)
    {
        if(boss(sef[m[k].i]) != boss(sef[m[k].j]))
        {
            unire(m[k].i, m[k].j);
            S += m[k].cost;
        }
        else
            m[k].cost = 1001;
    }
    g << S << '\n';
    g << N - 1 << '\n';
    for(int k = 1; k <= M; k++)
    {
        if(m[k].cost != 1001)
            g << m[k].i << " " << m[k].j << '\n';
    }
    return 0;
}