#include <bits/stdc++.h>
#define nmax 200005
#define mmax 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct trei{
    int nod1, nod2, cost;
};
struct dublu{
    int a, b;
};
bool cmp(trei x, trei y)
{
    return x.cost < y.cost;
}
int t[nmax], n, m, sum_min, nr;
trei muchii[mmax], var;
vector <dublu> sols;
dublu ceva;

int radacina(int k)
{
    int r, copie = k;
    while(t[k] != k)
        k = t[k];
    r = k;
    while(t[copie] != copie)
        copie = t[copie], t[copie] = r;
    return r;
}


int main()
{
    int i, a, b, c;
    fin >> n >> m;
    for(i = 0; i < m; i++)
    {
        fin >> a >> b >> c;
        var.nod1 = a, var.nod2 = b, var.cost = c;
        muchii[i] = var;
    }
    sort(muchii, muchii + m, cmp);
    for(i = 1; i <= n; i++)
        t[i] = i;
    for(i = 0; i < m; i++)
    {
        var = muchii[i];
        a = radacina(var.nod1);
        b = radacina(var.nod2);
        if(a != b)
        {
            t[b] = a;
            nr+=1;
            sum_min+=var.cost;
            ceva.a = var.nod1, ceva.b = var.nod2;
            sols.push_back(ceva);
        }
    }
    fout << sum_min << '\n';
    fout << nr << '\n';
    for(i = 0; i < nr; i++)
        fout << sols[i].a << " " << sols[i].b << '\n';
    return 0;
}