#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;

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

int n, m, total;
int culoare[200001];

void initialzare(int i){
    culoare[i] = i;
}
int reprezentant(int i){
return culoare[i];
}
void reuneste(int i, int j){
    int r1, r2;
    r1 = reprezentant(i);
    r2 = reprezentant(j);
    for(int k = 1; k<=n; k++)
        if(culoare[k]==r2)
            culoare[k] = r1;
}
int main()
{
    fin>>n>>m;
    vector<vector<int>> lista;
    for(int i = 0; i < m; i++){
       int x, y, c;
       fin>>x>>y>>c;
       lista.push_back({c, x, y});
    }
    sort(lista.begin(), lista.end());
    for(int i = 1; i <= n; i++)
        initialzare(i);
    vector<vector<int>> muchii;
    for(int i = 0; i < m && muchii.size()<n; i++){
        int r1 = lista[i][2];
        int r2 = lista[i][1];
        int c = lista[i][0];
        if(reprezentant(r1)!=reprezentant(r2)){
            //cout<<1;
            reuneste(r1, r2);
            muchii.push_back({r1, r2, c});
            total += c;
        }
    }
    fout<<total<<"\n";
    fout<<muchii.size()<<"\n";
    for(int i = 0; i < muchii.size(); i++){
        for(int j = 0; j < muchii[i].size()-1; j++)
        fout<<muchii[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}