//
//  main.cpp
//  Arbore partial de cost minim (infoarena)
//
//  Created by Andrei Bădulescu on 23.12.22.
//

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

using namespace std;

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

const int N = 200000;

struct edge {
    int x, y, cost;
};

vector <edge> edges;
vector <int> subset;

int master[N + 1];
int n, m, result;

bool comparisonArgument(edge lhs, edge rhs) {
    return lhs.cost < rhs.cost;
}

int find(int x) {
    if (master[x] == x) {
        return x;
    }
    
    int result = x;
    
    while (master[result] != result) {
        result = master[result];
    }
    
    while (master[x] != result) {
        int aux = master[x];
        master[x] = result;
        x = aux;
    }
    
    return result;
}

void connect(int x, int y) {
    x = find(x);
    y = find(y);
    
    if (x == y) {
        return;
    }
    
    master[x] = y;
}

int main() {
    cin >> n >> m;
    
    for (auto i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        
        edges.push_back({a, b, c});
    }
    
    for (auto i = 1; i <= n; i++) {
        master[i] = i;
    }
    
    sort(edges.begin(), edges.end(), comparisonArgument);
    
    for (auto i = 0; i < m; i++) {
        if (find(edges[i].x) != find(edges[i].y)) {
            connect(edges[i].x, edges[i].y);
            result += edges[i].cost;
            subset.push_back(i);
        }
    }
    
    cout << result << '\n' << n - 1 << '\n';
    
    for (auto index: subset) {
        cout << edges[index].x << ' ' << edges[index].y << '\n';
    }
    
    return 0;
}