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

using namespace std;

const int inf = 1000000;

int n, m;
vector<pair<int, int> > vecini[200005];
bool viz[200005];
int cost[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));
    }

    for(int i = 0; i <= n + 1; i++){
        cost[i] = inf;
    }
}

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

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

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

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

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

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