#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

struct{
    int x, y, cost;
}muchii[400005];

struct{
    int x, y;
}bune[400005];

int n, m, t[200005], s, k;

void citire()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
        fin >> muchii[i].x >> muchii[i].y >> muchii[i].cost;
}

void sortare(int st, int dr)
{
    int i = st, j = dr, m = muchii[(st + dr) / 2].cost;
    while(i <= j)
    {
        while(muchii[i].cost < m)
            i++;
        while(muchii[j].cost > m)
            j--;
        if(i <= j)
        {
            muchii[0] = muchii[i];
            muchii[i] = muchii[j];
            muchii[j] = muchii[0];
            i++;
            j--;
        }
    }
    if(st < j)
        sortare(st, j);
    if(dr > i)
        sortare(i, dr);
}

void initializare_tati()
{
    for(int i = 1; i <= n; i++)
        t[i] = i;
}

int main()
{
    citire();
    sortare(1, m);
    initializare_tati();
    for(int i = 1; i <= m; i++)
    {
        if(t[muchii[i].x] != t[muchii[i].y])
        {

            s += muchii[i].cost;
            int x = t[muchii[i].x], y = t[muchii[i].y];
            bune[++k].x = muchii[i].x;
            bune[k].y = muchii[i].y;
            for(int j = 1; j <= n; j++)
                if(t[j] == x)
                    t[j] = y;
        }
    }
    fout << s << '\n' << n - 1 << '\n';
    for(int i = 1; i <= k; i++)
        fout << bune[i].x << ' ' << bune[i].y << '\n';
}