#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);

    // while (nrNoduriVizitate < n){
    //     // alegem muchia de cost minim ale carei noduri nu au fost adaugate in APM
    //     int costMin = 1e9;
    //     int indMin;
    //     for (int j = 0; j < n; j++){
    //         if (vizitat[j] == false && costuri[j] < costMin){
    //             costMin = costuri[j];
    //             indMin = j;
    //         }
    //     }
    //     suma += costMin;
    //     vizitat[indMin] = true;
    //     nrNoduriVizitate++;

    //     for (int i = 0; i < lv[indMin].size(); i++){
    //         if (vizitat[lv[indMin][i].first] == false && lv[indMin][i].second < costuri[lv[indMin][i].first])
    //             parinte[lv[indMin][i].first] = indMin;
    //             costuri[lv[indMin][i].first] = lv[indMin][i].second;
    //     }
    // }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push(make_pair(0,0));
    int suma = 0;

    costuri[0] = 0;
    int nrNoduriVizitate = 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));
            }
            }
        }
}
    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 << endl;
    }
    return 0;
}