#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct Radu{
    int next, cost, acum;
    bool operator < ( const Radu &other ) const {
        return cost > other.cost;
    }
};

struct pereche{
    int prima, doua;
};
vector <Radu> graf[400001];
vector <pereche> sol;


bool viz[200001];

int dijkstra( int nod ){
    priority_queue <Radu> pq;
    int rez = 0;
    pq.push({nod, 0, 0});
    while( !pq.empty() ){
        nod = pq.top().next;
        int cost = pq.top().cost;
        int acum = pq.top().acum;
        pq.pop();
        if( viz[nod] )
            continue;
        rez += cost;
        sol.push_back({nod, acum});
        viz[nod] = true;
        for(Radu vecin: graf[nod])
            if( !viz[vecin.next] )
                pq.push({vecin.next, vecin.cost, nod});
    }
    return rez;
}
int main()
{
    int n, m;
    in >> n >> m;
    for( int i = 0; i < m; i++ ){
        int a, b, cost;
        in >> a >> b >> cost;
        graf[a].push_back({b, cost, a});
        graf[b].push_back({a, cost, b});
    }
    out << dijkstra(1) << "\n" << sol.size() - 1 << "\n";
    for( int i = 1; i < sol.size(); i++ )
        out << sol[i].prima << " " << sol[i].doua << "\n";
    return 0;
}