#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, sef[200001];
vector<pair<int, int>> rez;

int boss(int x){
    if(sef[x] == x)
        return x;
    return sef[x] = boss(sef[x]);
}

void unite(int x, int y){
    int sefx = boss(x), sefy = boss(y);
    sef[sefy] = sefx;
}

bool together(int x, int y){
    return boss(x) == boss(y);
}

struct nod{
    int x, y, c;
}v[200001];

bool cmp(nod a, nod b){
    return a.c < b.c;
}

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

void solve(){
    int cost = 0;
    sort(v + 1, v + m + 1, cmp);
    for(int i = 1; i <= n; i++)
        sef[i] = i;
    for(int i = 1; i <= m; i++){
        if(!together(v[i].x, v[i].y)){
            unite(v[i].x, v[i].y);
            cost += v[i].c;
            rez.push_back({v[i].x, v[i].y});
        }
    }
    fout << cost << "\n" << n - 1 << "\n";
    for(int i = 0; i < rez.size(); i++)
        fout << rez[i].first << " " << rez[i].second << "\n";
}

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