#include <fstream>
#include <vector>
#include "algorithm"
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

const int NMAX = 400005;

pair<int, int> P[NMAX];
int k;
int N, M, total;

vector<int> tati;
vector<int> rang;

struct Muchie{
    int nod1;
    int nod2;
    int cost;
} Vec[NMAX];

bool cmp(Muchie a, Muchie b){
    return (a.cost < b.cost);
}

int Find(int Nod){
    while(tati[Nod] != Nod){
        Nod = tati[Nod];
    }
    return Nod;
}

void Unire(int x, int y){
    if(rang[x] < rang[y])
        tati[x] = y;
    else if(rang[x] > rang[y])
        tati[y] = x;
    else if(rang[x] == rang[y]){
        tati[x] = y;
        rang[y]++;
    }

}

int main() {
    tati.resize(NMAX);
    rang.resize(NMAX);
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        cin >> Vec[i].nod1 >> Vec[i].nod2 >> Vec[i].cost;
    }
    sort(Vec, Vec + M + 1, cmp);
    for(int i = 1; i<= N; i++){
        tati[i] = i;
        rang[i] = 1;
    }
    for(int i = 1; i <= M; i++){
        int tata_nod1 = Find(Vec[i].nod1);
        int tata_nod2 = Find(Vec[i].nod2);
        if(Find(Vec[i].nod1) != Find(Vec[i].nod2)){
            Unire(tata_nod2, tata_nod1);
            P[++k].first = Vec[i].nod1;
            P[k].second = Vec[i].nod2;
            total += Vec[i].cost;
        }
    }
    cout << total << "\n";
    cout << N - 1 << "\n";
    for(int i = 1; i <= k; i++){
        cout << P[i].first << P[i].second << "\n";
    }
    return 0;
}