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

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX = 200005;
const int MMAX = 400005;

int n, m, t[NMAX], rang[NMAX], k, suma;

pair <int,int> arb[MMAX];

struct muchie{
    int x, y, cost;
}v[MMAX];

bool compara(muchie x, muchie y)
{
    return x.cost < y.cost;
}

int tatal(int nod)
{
    while(nod != t[nod])
        nod = t[nod];
    return nod;
}

void unire(int x, int y)
{

    if(rang[x] < rang[y])
        t[x] = y;
    if(rang[y] < rang[x])
        t[y] = x;
    if(rang[x] == rang[y]){
        t[x] = y;
        rang[y]++;
    }
}

void kruskal()
{
    for(int i = 1; i <= m; i++){
        int tx = tatal(v[i].x);
        int ty = tatal(v[i].y);

        if(tx != ty){
            unire(tx, ty);
            k++;
            arb[k].first = v[i].x;
            arb[k].second = v[i].y;
            suma += v[i].cost;
        }
    }

    fout << suma << "\n" << n-1 << "\n";
    for(int i = 1; i <= k; i++)
        fout << arb[i].first << " " << arb[i].second << "\n";
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
        fin >> v[i].x >> v[i].y >> v[i].cost;
    sort(v+1, v+m+1, compara);

    for(int i = 1; i <= n; i++){
        t[i] = i;
        rang[i] = 1;
    }

    kruskal();

    return 0;
}