#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

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

const int NMax = 400005;
const int inf = 0x3f3f3f3f;

int n, m, x[NMax], y[NMax], cost[NMax], indx[NMax];
int rang[NMax / 2], daddy[NMax / 2];

int Find(int x)
{
    int y = x, dad;
    for(x; daddy[x] != x; x = daddy[x]);
    dad = daddy[x];
    while(y != dad) {
        x = daddy[y];
        daddy[y] = dad;
        y = x;
    }
    return dad;
}

void Union(int x, int y)
{
    if(rang[x] > rang[y])
        daddy[y] = x;
    else
        daddy[x] = y;

    if(rang[x] == rang[y])
        rang[y]++;
}

bool cmp(const int& a, const int& b)
{
    return cost[a] < cost[b];
}

int main()
{
    int total = 0;
    vector < pair < int, int > > apm;
    f >> n >> m;
    for(int i = 1; i <= n; ++i) {
        rang[i] = 1;
        daddy[i] = i;
    }
    for(int i = 1; i <= m; ++i) {
        f >> x[i] >> y[i] >> cost[i];
        indx[i] = i;
    }
    sort(indx + 1, indx + m + 1, cmp);
    for(int j = 1; j <= m; ++j) {
        int i = indx[j];
        if(Find(x[i]) != Find(y[i])) {
            Union(Find(x[i]), Find(y[i]));
            total += cost[i];
            apm.push_back({x[i], y[i]});
        }
    }
    g << total << '\n' << n - 1 << '\n';
    for(int i = 0; i < apm.size(); ++i)
        g << apm[i].first << ' ' << apm[i].second << '\n';

}