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

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, c, t[200001], ind;

struct Muchie
{
    int x, y, cost;
}v[400001], rez[200000];

bool Compare(Muchie a, Muchie b)
{
    return a.cost < b.cost;
}

void input()
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i)
        fin >> v[i].x >> v[i].y >> v[i].cost;
    sort(v + 1, v + m + 1, Compare);
    for(int i = 1; i <= n; ++i)
        t[i] = i;
}

void Solve()
{
    int k = 0, i = 1;
    while(k < n - 1)
    {
        int x = v[i].x, y = v[i].y;
        if(t[x] != t[y])
        {
            c += v[i].cost;
            rez[++ind].x = y, rez[ind].y = x;
            int tx = t[x], ty = t[y];
            for(int j = 1; j <= n; ++j)
                if(t[j] == ty)
                    t[j] = tx;
            k++;
        }
        i++;
    }
}

void output()
{
    fout << c << '\n' << n - 1 << '\n';
    for(int i = 1; i <= ind; ++i)
        fout << rez[i].x << ' ' << rez[i].y << '\n';
}

int main()
{
    input();
    Solve();
    output();
    return 0;
}