#include <bits/stdc++.h>
using namespace std;
const int nmx = 200'000;
vector<array<int,3>> edg;
int t[nmx];
int g[nmx];
#define cin fin
#define cout fout
ifstream fin("apm.in");
ofstream fout("apm.out");
int root(int k){
    int it = k;
    while(it!=t[it]){
        it = t[it];
    }
    t[k] = it;
    return it;
}

int unite(int n1, int n2){
    int r1 = root(n1), r2 = root(n2);
    if(r1 != r2){
        if(g[r1] == g[r2]){
            g[r1]++;
            t[r2] = r1;
        }
        else if(g[r1] > g[r2])
            t[r2] = r1;
        else
            t[r1] = r2;
        return 1;
    }
    else
        return 0;
}

int main(){
    for(int i=1;i<nmx;i++)
        t[i] = i;
    int n,m;
    cin >> n >> m;
    while(m--){
        array<int,3> ed;
        cin >> ed[1] >> ed[2] >> ed[0];
        edg.push_back(ed);
    }
    sort(edg.begin(),edg.end());
    vector<array<int,2>> ans;
    int w = 0, cnt = 0;
    for(auto& ed : edg){
        if(cnt == n-1)
            break;
        int u = ed[1], v = ed[2];
        if(unite(u,v)){
            cnt++;
            w += ed[0];
            ans.push_back({u,v});
        }
    }
    cout << w << "\n";
    cout << n-1 << "\n";
    for(auto& ed : ans)
        cout << ed[0] << " " << ed[1] << "\n";
}