#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct punct
{
    int x, y, c;
}u[200002], sol[200002];
 
int n, m, k, i, ct, j, p[200002], t[200002];
 
bool cmp(punct x, punct y)
{
    return (x.c < y.c);
}
 
int root (int x)
{
    while (x != t[x]) 
		x = t[x];
    return x;
}
 
void unifica(int x, int y)
{
    if (p[x] < p[y]) 
		t[x] = y;
    if (p[x] > p[y]) 
		t[y] = x;
    if (p[x] == p[y])
	{
        t[y] = x;
        p[x]++;
    }
}
 
int main ()
{
    f >> n >> m;
    for (i = 1; i <= m; i++)
	{
        f >> u[i].x >> u[i].y >> u[i].c;
        t[i] = i;
    }
    sort(u + 1, u + m + 1, cmp);
    i = 1;
    while (k < n  - 1)
	{
        int rx = root(u[i].x);
        int ry = root(u[i].y);
        if (rx != ry){
            k++;
            ct += u[i].c;
            sol[k] = u[i];
            unifica(rx, ry);
        }
        i++;
    }
 
    g << ct << "\n" << k << "\n";
    for (i = 1; i <= k; i++) 
		g << sol[i].y << " " << sol[i].x << "\n";
}