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

using namespace std;

int n, m;
vector<pair<int, int> > vecini[200005];
bool viz[200005];
priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > Q;
pair<int, int> sol[200005];
int nr = 0;

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({tmp3, tmp2});
        vecini[tmp2].push_back({tmp3, tmp1});
    }
}

void solve(){
    Q.push({0, {0, 0}});

    int s = 0;

    while(!Q.empty()){
        int d = Q.top().first;
        int x = Q.top().second.first;
        int y = Q.top().second.second;

        Q.pop();

        if(viz[x] == true){
            continue;
        }

        sol[nr] = {x, y};
        nr++;
        viz[x] = true;

        s += d;

        int l = vecini[x].size();
        for(int i = 0; i < l; i++){
            Q.push({vecini[x][i].first, {vecini[x][i].second, x}});
        }
    }

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

    for(int i = 1; i < nr; i++){
        printf("%d %d\n", sol[i].first + 1, sol[i].second + 1);
    }
}

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

    citire();
    solve();

    return 0;
}