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

using namespace std;

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

const int MAX = 200005;

int n, m, cost, p[MAX];
vector < pair < int, int > > rasp;

struct muchie{

    int x;
    int y;
    int c;
}G[MAX];

bool cmp(muchie a, muchie b){

    return a.c < b.c;
}

int parinte(int nod){

    if(p[nod] == nod)
        return nod;
    return p[nod] = parinte(p[nod]);
}

void unite(int x, int y){

    p[parinte(x)] = parinte(y);
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i)
        fin >> G[i].x >> G[i].y >> G[i].c;

    for(int i = 1; i <= n; ++i)
        p[i] = i;

    sort(G + 1, G + m + 1, cmp);

    for(int i = 1; i <= m; ++i){
        if(parinte(G[i].x) != parinte(G[i].y)){
            unite(parinte(G[i].x), parinte(G[i].y));
            cost += G[i].c;
            rasp.push_back(make_pair(G[i].x, G[i].y));
        }
    }

    fout << cost << '\n';
    fout << rasp.size() << '\n';
    for(int i = 0 ; i < rasp.size(); i++){
        fout << rasp [ i ] . first << ' ' << rasp [ i ] . second << '\n';
    }

    return 0;
}