#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define VMAX 200005
#define INF INT_MAX

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

int V, E, dist[VMAX], cf;
bool v[VMAX];
vector<pair<int, int>> adj[VMAX], apm;
priority_queue<pair<int, pair<int, int>>> pq;

int main(){
    f >> V >> E;
    for(int i = 1; i <= E; i++){
        int x, y, cost;
        f >> x >> y >> cost;
        adj[x].push_back({y, cost});
        adj[y].push_back({x, cost});
    }
    for(int i = 1; i <= V; i++)
        dist[i] = INF;

    pq.push({0, {1, 1}});
    dist[1] = 0;

    while(!pq.empty()){
        int x = pq.top().second.first;
        int alfa = pq.top().second.second;
        int c = -pq.top().first;
        pq.pop();

        if(v[x] == 1) continue;

        v[x] = 1;
        cf += c;
        apm.push_back({alfa, x});

        for(auto& t : adj[x]){
            int y = t.first;
            int z = t.second;

            if(v[y] == 0 && dist[y] > z){
                pq.push({-z, {y, x}});
                dist[y] = z;
            }
        }
    }

    g << cf << '\n' << V - 1 << '\n';
    for(int i = 1; i < V; i++)
        g << apm[i].first << ' ' << apm[i].second << '\n';

    return 0;
}