#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int MAXN = 2*1e5 + 50;
vector <pair < int, pair <int, int>>> g;
vector <pair<int, int>> ans;
int father[MAXN], sizee[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(a == b) return;
    if(sizee[a] < sizee[b])
        swap(a ,b);
    father[b] = a;
    sizee[a] += sizee[b];
}
int main(){
    int n, m, cnt = 0, copie ;
    fin >> n >> m;
    copie = n;
    for(int i = 1; i <= n; ++i)
        sizee[i] = 1, father[i] = i;
    for(int i = 0; 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;
        if(findd(x) != findd(y))
            unionn(x, y), cnt += g[i].first, n--, ans.push_back({x, y});
    }
    fout << cnt << '\n' << copie - 1 << '\n' ;
    for(auto x : ans)
        fout << x.second << " " << x.first << '\n';
    return 0;
}