#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
typedef unsigned long long ll;
typedef pair < int , int > PII;
typedef pair < int , PII >  PIPII;

int n, m, Dad[200100], Rang[200100], rs;
vector < PIPII > V;
vector < PII > Ans;

int find(int x){
    return (x == Dad[x] ? x : find(Dad[x]));
}

void unite(PII El){
    int x = find(El.first);
    int y = find(El.second);

    if (Rang[x] > Rang[y]) swap(x, y);
    Dad[x] = y;
    Rang[y] += Rang[x];
}

int main(){
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) Dad[i] = i, Rang[i] = 1;

    for (int x, y, c; m; m--){
        cin >> x >> y >> c;
        V.push_back({c, {x, y}});
    }

    sort(V.begin(), V.end());

    for (auto it : V){
        if (find(it.second.first) == find(it.second.second)) continue;
        rs += it.first;
        Ans.push_back(it.second);
        unite(it.second);
    }

    cout << rs << "\n" << n - 1 << "\n";
    for (auto it : Ans){
        cout << it.first << " " << it.second << "\n";
    }

    return 0;
}