#include <iostream>
#include <fstream>
#include <algorithm>

#define maxn 200005
#define maxn1 400005

using namespace std;
    ifstream in("apm.in");
    ofstream out("apm.out");

struct muchie{
    int x, y, c;}graf[maxn1], v[maxn];

int t[maxn];
int n, m, x, y, sum, q;

int radacina(int x)
{
    if(t[x] == 0)
            return x;
    t[x] = radacina(t[x]);
            return t[x];
}
int reuneste(int x, int y)
{
    t[radacina(y)] = radacina(x);
}

int cmp(muchie x, muchie y)
{
    return x.c < y.c;
}

int main()
{
    in >> n >> m;

    for(int i = 0; i < m; i++)
        in >> graf[i].x >> graf[i].y >> graf[i].c;

    sort(graf, graf+m, cmp);

    for(int i = 0; i < m && q < n -1; i++)
        if(radacina(graf[i].x) != radacina(graf[i].y))
            {   sum += graf[i].c;
                reuneste(graf[i].x, graf[i].y);
                v[q++] =  graf[i];
            }

    out << sum << "\n" << q <<"\n";
    for(int i = 0; i < q; i++)
        out << v[i].y << " " << v[i].x << "\n";
    return 0;
}