#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

#define inf 10000
#define NMAX 200003

vector< int > graph[NMAX], graphC[NMAX];
priority_queue <pair <int, pair<int, int> > > myheap;

pair <int, pair<int, int> > best;

int n, m, dist[NMAX], viz[NMAX], tata[NMAX], cost, sursa, i, index, nrMuchii;

void citire()
{
    f>>n>>m;

    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        f>>a>>b>>c;
        /// muchie de la a->b
        graph[a].push_back(b);

        /// costul muchiei de la a->b
        graphC[a].push_back(c);
    }

}
pair<int, int> muchie;
pair<int, int> arbore[10000];

void algoritmPrim(){

    cost = 0;
    sursa = 1;
    viz[sursa] = 1;
    tata[sursa] = 0;

    for(i = 0; i < graph[sursa].size(); i ++)
        myheap.push(make_pair(-graphC[sursa][i], make_pair(sursa,graph[sursa][i])));

    for(i = 1; i <= n; i ++){
        best = myheap.top();
        myheap.pop();

        muchie = best.second;
        int nod2 = muchie.second;
        int nod1 = muchie.first;

        if(viz[nod2] == 0)
        {
        tata[nod2] = nod1;
        cout<< nod1<< " "<< nod2<< " "<< -best.first<<endl;
        cost += (-best.first);
        viz[nod2] = 1;

        for(int j = 0; j < graph[nod2].size(); j ++)
                myheap.push(make_pair(-graphC[nod2][j], make_pair(nod2,graph[nod2][j])));}

    }

}

void afisare(){
    g<<cost<<endl;
    g<< n-1 <<endl;
    for(int i = 2; i <= n; i ++)
        g<< i<< " "<<tata[i]<<endl;
}
int main()
{
    citire();
    algoritmPrim();
    afisare();
    return 0;
}