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

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct edge
{
    int s,d,c;
    edge(int s = 0, int d = 0, int c = 0):s(s),d(d),c(c){}

};
bool mycompare(const edge &a, const edge &b)
{
    return a.c < b.c;
}
vector <edge> edges;
vector <edge> solution;
int r[200001];
int n,m;

void Init(int i)
{
    r[i] = i;
}
int Repr(int i)
{
    return r[i];
}
void Union(int a, int b)
{
    int r1 = Repr(a);
    int r2 = Repr(b);

    for(int i = 1; i <= n; i ++)
        if(r[i] == r2)
        r[i] = r1;
}
int main()
{

    fin>>n>>m;
    for(int i = 0; i < m; i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        edges.push_back(edge(x,y,c));
    }
    sort(edges.begin(),edges.end(),mycompare);
    for(int i = 1; i<= n; i++)
    {
        Init(i);
    }
    int countSel = 0, cost = 0;
    for(auto &ed: edges)
    {
        if(Repr(ed.s)!=Repr(ed.d))
        {
            solution.push_back(ed);
            cost += ed.c;
            countSel ++;
            ///marchez faptul ca acum cele doua componente s-au unit - toate nodurile au acelasi reprezentant/culoare
            Union(ed.s,ed.d);
            ///solutia este gata
            if(countSel == n - 1) break;
        }

    }
    fout << cost << "\n";
    fout << solution.size() << "\n";
    for(auto &ed: solution)
    {
        fout<<ed.s << " " << ed.d << " " << ed.c << "\n";
    }
    return 0;
}