#include <fstream>
#include <algorithm>
#include <vector>
#define MAX 400005

using namespace std;

int n, m;
int gr[MAX], x[MAX], y[MAX], c[MAX], ind[MAX], ans;
vector<int> v;

void read();
bool comp(int i, int j);
void solve();
int grupa(int i);

int main(){
    read();
    solve();
    return 0;
}

void read(){
    ifstream fin ("apm.in");
    fin >> n >> m;
    for (int i = 1; i <= m; ++i){
        fin >> x[i] >> y[i] >> c[i];
        ind[i] = i;
    }

    for (int i = 1; i <= n; ++i)
        gr[i] = i;
    sort(ind + 1, ind + m + 1, comp);

    fin.close();
}

bool comp(int i, int j){
    return (c[i] < c[j]);
}

void solve(){
    for (int i = 1; i <= m; ++i){
        if (grupa(x[ind[i]]) != grupa(y[ind[i]])){
            ans += c[ind[i]];
            gr[grupa(x[ind[i]])] = grupa(y[ind[i]]);
            v.push_back(ind[i]);
        }
    }

    ofstream fout ("apm.out");
    fout << ans << "\n" << n-1 << "\n";
    for (int i = 0; i < n-1; ++i)
        fout << x[v[i]] << " " << y[v[i]] << "\n";

    fout.close();
}

int grupa(int i){
    if (gr[i] == i)
        return i;
    gr[i] = grupa(gr[i]);
    return gr[i];
}