#include <bits/stdc++.h>

using namespace std;

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

int n, m, t[200001], tip, x, y, s[200001], sum, nr;

struct muchie
{
    int x, y, c;
}v[200001], sol[200001];

int cond(muchie a, muchie b)
{
    return a.c < b.c;
}

int root(int x)
{
    while(t[x] != 0)
        x = t[x];
    return x;
}

void unite(int x, int y)
{
    int rx = root(x);
    int ry = root(y);
    if(rx != ry)
    {
        if(s[rx] == s[ry])
        {
            t[ry] = rx;
            s[rx]++;
        }
        else if(s[rx] > s[ry])
            t[ry] = rx;
        else t[rx] = ry;
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> v[i].x >> v[i].y >> v[i].c;
    }
    sort(v + 1, v + m + 1, cond);
    for(int i = 1; i <= m && nr != n - 1; i++)
    {
        if(root(v[i].x) != root(v[i].y))
        {
            unite(v[i].x, v[i].y);
            nr++;
            sum += v[i].c;
            sol[nr] = v[i];
        }
    }
    fout << sum << '\n';
    fout << n - 1 << '\n';
    for(int i = 1; i <= n - 1; i++)
    {
        fout << sol[i].x << " " << sol[i].y << '\n';
    }

    return 0;
}