#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int MAXN = 200010;
vector <pair<int, pair<int,int>>> g;
vector <pair <int, int>> ans;
int sizee[MAXN], father[MAXN];
int findd(int node){
    if(node == father[node]) return node;
    return father[node] = findd(father[node]);
}
void unionn(int x, int y){
    int a = findd(x), b = findd(y);
    if(sizee[a] < sizee[b]) swap(a, b);
    father[b] = a;
    sizee[a] += sizee[b];
}
int main(){
    int n, m, total = 0; fin >> n >> m;
    for(int i = 1; i <= n; ++i)
        sizee[i] = 1, father[i] = i;
    for(int i = 1; i <= m; ++i){
        int x, y, cost; fin >> x >> y >> cost;
        g.push_back({cost, {x, y}});
    }
    sort(g.begin(), g.end());
    for(int i = 0; i < m and n > 1; ++i){
        int x = g[i].second.first;
        int y = g[i].second.second;
        int cost = g[i].first;
        if(findd(x) != findd(y)){
            unionn(x, y);
            n--;
            total += cost;
            ans.push_back({x, y});
        }
    }
    fout << total << '\n' << ans.size() << '\n';
    for(auto x : ans)
        fout << x.first << " " << x.second << '\n';
    return 0;
}