#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

vector< pair<int,int> > L[200001];
int d[200001];    
int p[200001];    
bool vis[200001]; 

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

    int N, M;
    fin >> N >> M;

    for (int i = 0; i < M; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        L[x].push_back({y, c});
        L[y].push_back({x, c});
    }


    for (int i = 1; i <= N; i++) {
        d[i] = INT_MAX; 
        p[i] = 0;
        vis[i] = false;
    }

d[1] = 0;
p[1] = 0;


    priority_queue< pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > PQ;
    PQ.push({d[1], 1});

    long long sol = 0;

    while (!PQ.empty()) {
        int nod = PQ.top().second;
        int cost = PQ.top().first;
        PQ.pop();

        if (vis[nod]) {
            continue;
        }

        vis[nod] = true;
        sol += cost;

        for (auto v : L[nod]) {
            int x = v.first;
            int c = v.second;

            if (!vis[x] && c < d[x]) {
                d[x] = c;
                p[x] = nod;
                PQ.push({d[x], x});
            }
        }
    }

    fout << sol << "\n";
    fout << N - 1 << "\n";
    for (int i = 2; i <= N; i++) {
        fout << i << " " << p[i] << "\n";
    }

    fin.close();
    fout.close();

    return 0;
}