#include<bits/stdc++.h>
using namespace std;

const int NMAX = 2e5 + 5, MMAX = 4e5 + 5;
int n, m, parent[NMAX], sz[NMAX];
vector<pair<int, pair<int, int>>> edges;
vector<pair<int, int>> ansEdges;

void cer1(int a, int b);
bool cer2(int x, int y);

int find(int x) {
    while(x != parent[x])
        x = parent[x];
    return x;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    int c, a, b;
    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        parent[i] = i;
        sz[i] = 1;
    }

    for(int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges.push_back({c, {a, b}});
    }

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

    int ans = 0;
    for(auto u : edges) {
        if(cer2(u.second.first, u.second.second) == false) {
            cer1(u.second.first, u.second.second);
            ans += u.first;
            ansEdges.push_back({u.second.first, u.second.second});
        }
    }

    cout << ans << "\n";
    cout << ansEdges.size() << "\n";
    for(auto u : ansEdges) {
        cout << u.first << " " << u.second << "\n";
    }
}

void cer1(int x, int y) {
     while(x != parent[x])
        x = parent[x];
     while(y != parent[y])
        y = parent[y];
    if(sz[x] > sz[y]) {
        sz[x]++;
        parent[y] = x; 
    }
    else {
        sz[y]++;
        parent[x] = y;
    }
}

bool cer2(int x, int y) {
    while(x != parent[x])
        x = parent[x];
     while(y != parent[y])
        y = parent[y];
    return parent[x] == parent[y];
}