#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct Muchie
{
    int a, b, c;
} vm[400000];

bool cmp(const Muchie& a, const Muchie& b)
{
    return a.c < b.c;
}

int res[400000];
vector<int> v[200000];

int tata(int n)
{
    if(v[n].size() == 0)
        return n;
    return tata(v[n][0]);
}

int main()
{
    int n, m, a, b, c, i, r = 2, ta, tb, sum;
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i = 0; i < m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        vm[i].a = a - 1;
        vm[i].b = b - 1;
        vm[i].c = c;
    }
    sort(vm, vm + m, cmp);
    ta = tata(vm[0].a);
    tb = tata(vm[0].b);
    v[ta].push_back(tb);
    res[0] = 0;
    ta = tata(vm[1].a);
    tb = tata(vm[1].b);
    v[ta].push_back(tb);
    res[1] = 1;
    sum = vm[0].c + vm[1].c;
    for(i = 2; i < m; i++)
    {
        ta = tata(vm[i].a);
        tb = tata(vm[i].b);
        if(ta != tb)
        {
            v[ta].push_back(tb);
            sum += vm[i].c;
            res[r++] = i;
            if(r == n - 1)
                break;
        }
    }
    printf("%d\n%d\n", sum, r);
    for(i = 0; i < r; i++)
    {
        printf("%d %d\n", vm[res[i]].b + 1, vm[res[i]].a + 1);
    }
    return 0;
}