#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int n, m;
vector<pair<int, int> > vecini[200005];
bool viz[200005];
int tata[200005];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pk;

void citire(){
    scanf("%d %d", &n, &m);

    int tmp1, tmp2, tmp3;

    for(int i = 0; i < m; i++){
        scanf("%d %d %d", &tmp1, &tmp2, &tmp3);
        tmp1--;
        tmp2--;
        vecini[tmp1].push_back(make_pair(tmp3, tmp2));
        vecini[tmp2].push_back(make_pair(tmp3, tmp1));
    }
}

void solve(){
    pk.push(make_pair(0, 0));

    int nr = 0;
    int sol = 0;
    vector<pair<int, int> > solutii;

    while(pk.empty() == false){
        int nodCurent = pk.top().second;
        if(viz[nodCurent] == true){
            pk.pop();
            continue;
        }
        sol += pk.top().first;
        nr++;
        pk.pop();
        viz[nodCurent] = true;

        int l = vecini[nodCurent].size();

        for(int i = 0; i < l; i++){
            if(viz[vecini[nodCurent][i].second] == false){
                pk.push(vecini[nodCurent][i]);
                tata[vecini[nodCurent][i].second] = nodCurent;
            }
        }
    }

    printf("%d", sol);
    printf("\n%d\n", n - 1);

    for(int i = 1; i < n; i++){
        printf("%d %d\n", i + 1, tata[i] + 1);
    }
}

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    citire();
    solve();


    return 0;
}