#include <bits/stdc++.h>
using namespace std;
int n, m, i, t[400005], nr_comp_con, k;
long long sum;
struct muchie
{
    int x, y, c;
}v[400005], muchii_ramase[400005];
int father(int x)
{
    int y = x;
    while(x != t[x])x = t[x];
    while(y != x)
    {
        int aux = t[y];
        t[y] = x;
        y = aux;
    }
    return x;
}
bool cmp(muchie a, muchie b)
{
    return a.c < b.c;
}
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].c;
    for(i = 1; i <= n; i ++)
        t[i] = i;
    sort(v + 1, v + m + 1, cmp);
    nr_comp_con = n;
    for(i = 1; i <= m; i ++)
        if(father(v[i].x) != father(v[i].y))
        {
            sum = sum + v[i].c;
            k ++;
            muchii_ramase[k] = v[i];
            t[father(v[i].x)] = father(v[i].y);
            nr_comp_con --;
            if(nr_comp_con == 1)break;
        }
    g << sum << "\n";
    g << k << "\n";
    for(i = 1; i <= k; i ++)
        g << muchii_ramase[i].x << " " << muchii_ramase[i].y << "\n";
    return 0;
}