#include <bits/stdc++.h>
using namespace std;
int n , m, i, t[200005], ct, s, val1, val2;
bool viz[500005];
struct muchie
{
    int x;
    int y;
    int cost;
}v[400005];
bool cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}
int faind(int x)
{
    int y = x, val;
    while(t[x] != x)x = t[x];
    while(x != y)
    {
        val = y;
        y = t[y];
        t[val] = x;
    }
    return x;
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    f >> n >> m;
    for(i = 1;i <= m;i++)
        f >> v[i].x >> v[i].y >> v[i].cost;
    for(i = 1;i <= n;i++)
        t[i] = i;
    sort(v + 1, v + m + 1, cmp);
    for(i = 1;i <= m && ct < n - 1;i++)
        if(faind(v[i].x) != faind(v[i].y))
        {
            s = s + v[i].cost;
            val1 = faind(v[i].x);
            val2 = faind(v[i].y);
            t[val1] = val2;
            viz[i] = true;
            ct++;
        }
    g << s << "\n";
    g << ct << "\n";
    for(i = 1;i <= m;i++)
        if(viz[i] == true)
        {
            g << v[i].y << " " << v[i].x << "\n";
        }
    return 0;
}