#include <bits/stdc++.h>
using namespace std;

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

    int n, m, nod1, nod2, cost;

    f >> n >> m;
    vector<vector<pair<int, int>>> lv;

    for (int i = 0; i < n; i++){
        vector<pair<int,int>> aux;
        lv.push_back(aux);
    }
    
    for (int i = 0; i < m; i++){
        f >> nod1;
        f >> nod2;
        f >> cost;
        lv[nod1 - 1].push_back(make_pair(nod2 -1, cost));
        lv[nod2 - 1].push_back(make_pair(nod1 -1, cost));
    }

    vector<int> parinte(n, -1);
    vector<int> costuri(n,  1e9);
    vector<bool> vizitat(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push(make_pair(0,0));
    costuri[0] = 0;

    while (pq.empty() == false) {
        int nod = pq.top().second;
        pq.pop();

        if(vizitat[nod] == false){
            vizitat[nod] = true;
            for (int i = 0; i < lv[nod].size(); i++){
                int nodVecin = lv[nod][i].first;
                int cost = lv[nod][i].second;

                if (vizitat[lv[nod][i].first] == false && lv[nod][i].second < costuri[nodVecin]){
                    parinte[nodVecin] = nod;
                    costuri[nodVecin] = cost;
                    pq.push(make_pair(costuri[nodVecin], nodVecin));
            }
            }
        }
}
    int suma = 0;
    for (int i = 1; i < n; i++)
        suma += costuri[i];

    g << suma << "\n";
    g << n - 1 << "\n";

    for (int i = 1; i < n; i++){   
        g << parinte[i] + 1 << " "  << i + 1 << "\n";
    }
    return 0;
}