#include <fstream>
#include <vector>
#include <algorithm>
#define N 100000
using namespace std;

ifstream cin ("apm.in");
ofstream cout ("apm.out");

int tata[2 * N + 1];
int cnt[2 * N + 1];

int rad(int x){
    if (tata[x] == 0) return x;
    else tata[x] = rad(tata[x]);
    return tata[x];
}

bool query(int x, int y){
    return (rad(x) == rad(y));
}

void merge(int x, int y){
    x = rad(x);
    y = rad(y);
    
    if (x == y) return ;
    
    if (cnt[x] > cnt[y]) swap(x, y);
    
    tata[x] = y;
    cnt[y] += cnt[x];
}

vector<pair<int, pair<int, int>>> muchii;

int main(){
    int n, m; cin >> n >> m;
    
    for(int i = 1; i <= n; i++){
        tata[i] = 0;
        cnt[i] = 1;
    }
    
    for(int i = 1; i <= m; i++){
        int a, b, c; cin >> a >> b >> c;
        muchii.push_back({c, {a, b}});
    }
    
    sort(muchii.begin(), muchii.end());
    
    long long ans = 0;
    vector<pair<int, int>> mans;
    
    for(int i = 0; i < muchii.size(); i++){
        int a = muchii[i].second.first, b = muchii[i].second.second;
        
        if (rad(a) == rad(b)) continue;
        
        ans += muchii[i].first;
        mans.push_back({a, b});
        
        merge(a, b);
    }
    
    cout << ans << endl << n - 1 << endl;
    
    for(int i = 0; i < mans.size(); i++)
        cout << mans[i].first << ' ' << mans[i].second << '\n';
        
    return 0;
}