#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n, m, suma_minima;
int tati[200001], lungime[200001];
vector<pair<int, pair<int, int>>> adiacenta;
vector<pair<int, int>> rasp;

void citire()
{
    f >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int x,y,c;
        f >> x >> y >> c;
        adiacenta.push_back({c, {x, y}});
    }
}

void afisare()
{
    g << suma_minima << endl << rasp.size();
    for (auto x: rasp)
    {
        g << endl << x.first << " " << x.second;
    }
}

int rad1(int x)
{
    if (tati[x] == x)
        return x;
    int rad = rad1(tati[x]);
    tati[x] = rad;
    return rad;
}

void reunire(int x, int y)
{
    int rad0 = rad1(x), rad2 = rad1(y);
    if (lungime[rad0] > lungime[rad2])
        tati[rad2] = rad0;
    else if(lungime[rad0]<lungime[rad2])
    {
        tati[rad0] = rad2;

    }
    else
    {
        tati[rad0] = rad2;
        lungime[rad2]++;
    }
}

void alg()
{
    for (int i = 1; i <= n; i++)
        tati[i] = i;
    for (auto x: adiacenta)
    {
        if (rad1(x.second.first) == rad1(x.second.second))
            continue;

        reunire(x.second.first, x.second.second);
        suma_minima += x.first;
        rasp.push_back(x.second);
    }
}


int main()
{
    citire();
    sort(adiacenta.begin(), adiacenta.end());
    alg();
    afisare();
    return 0;
}