#include <bits/stdc++.h>
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';

}