#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define FILE_NAME "apm"
const int N_MAX = 200005;
using Edge = pair< int, pair<int, int> >;

int N, M;
vector<int> g[N_MAX];
Edge edges[N_MAX * 2];
int t[N_MAX], deg[N_MAX];
vector<int> tree;
int sol;

void init() {
    freopen(FILE_NAME ".in", "r", stdin);
    
    scanf("%d %d", &N, &M);
    for (int i { 1 }; i <= M; ++i)
        scanf("%d %d %d", &edges[i].second.first, &edges[i].second.second, &edges[i].first);
    
    sort(edges + 1, edges + 1 + M);
    
    for (int i { 1 }; i <= N; ++i) {
        t[i] = i;
        deg[i] = 1;
    }
    
    fclose(stdin);
}

int root(int node) {
    int r;
    for (r = node; r != t[r]; r = t[r]);
    
    for (int dad; t[node] != node; node = dad) {
        dad = t[node];
        t[node] = r;
    }
    
    return r;
}

void unite(int a, int b) {
    if (deg[a] > deg[b]) {
        deg[a] += deg[b];
        t[b] = a;
    } else {
        deg[b] += deg[a];
        t[a] = b;
    }
}

void solve() {
    for (int i = 1; i <= M; ++i) {
        int x = edges[i].second.first, y = edges[i].second.second;
        
        if (root(x) != root(y)) {
            unite(root(x), root(y));
            tree.push_back(i);
            sol += edges[i].first;
        }
    }
}


void print() {
    freopen(FILE_NAME ".out", "w", stdout);
    
    printf("%d\n%d\n", sol, int(tree.size()));
    for (const auto& e : tree)
        printf("%d %d\n", edges[e].second.first, edges[e].second.second);
    
    fclose(stdout);
}

int main() {
    init();
    solve();
    print();
}