#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);
    int suma = 0;

    costuri[0] = 0;
    int nrNoduriVizitate = 0;

    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;
        }
        
    }

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


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