#include <bits/stdc++.h>
#define N 400005

using namespace std;

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

struct graf
{
    int a, b, cost;
}V[N];

int n, m, cost_tot, k;
int TT[N / 2];
pair <int, int> ans[N];

bool cmp(graf x, graf y)
{
    return x.cost < y.cost;
}

int Find(int nod)
{
    int rad = nod;
    while (TT[rad] != rad)
        rad = TT[rad];
    while (TT[nod] != nod)
    {
        int cpy = nod;
        nod = TT[nod];
        TT[cpy] = rad;
    }

    return rad;
}

void Union(int x, int y)
{
    int rad_x = Find(x);
    int rad_y = Find(y);
    TT[rad_y] = rad_x;

}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> V[i]. a >> V[i].b >> V[i].cost;

    sort(V + 1, V + m + 1, cmp);

    for (int i = 1; i <= n; i++)
        TT[i] = i;

    for (int i = 1; i <= m; i++)
    {
        if (Find(V[i].a) != Find(V[i].b))
        {
            cost_tot += V[i].cost;
            Union(V[i].a, V[i].b);
            ans[++k] = make_pair(V[i].a, V[i].b);
        }
    }

    fout << cost_tot << "\n";
    fout << k << "\n";
    for (int i = 1; i <= k; i++)
        fout << ans[i].first << " " << ans[i].second << "\n";
    return 0;
}