#include <bits/stdc++.h>
#define Nmax 400005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int n, m, X[Nmax], Y[Nmax], C[Nmax], rang[Nmax], dad[Nmax], v[Nmax], cnt;
vector <int> ans;

void read()
{
    f >> n >> m;
    for (int i = 1; i <= m; ++i) {
        f >> X[i] >> Y[i] >> C[i];
        v[i] = i;
    }
}

bool comp(int a, int b)
{
    return C[a] < C[b];
}

void vsort()
{
    sort(v + 1, v + m + 1, comp);
}

void init()
{
    for (int i = 1; i <= n; ++i) {
        dad[i] = i;
        rang[i] = 1;
    }
}

void unite(int x, int y)
{
    if (rang[dad[x]] < rang[dad[y]])
        dad[dad[x]] = dad[y];
    else
        dad[dad[y]] = dad[x];

    if (rang[dad[x]] == rang[dad[y]])
        rang[dad[y]]++;
}

void find(int node)
{
    int root = node;
    while (dad[root] != root)
        root = dad[root];

    int x = node, y;
    while (dad[x] != x) {
        y = dad[x];
        dad[x] = root;
        x = y;
    }
}

void solve()
{
    for (int i = 1; i <= m; ++i) {
        int it = v[i];
        find(X[it]);
        find(Y[it]);
        if (dad[X[it]] != dad[Y[it]]) {
            unite(X[it], Y[it]);
            cnt += C[it];
            ans.push_back(it);
        }
    }
}

void show()
{
    g << cnt << "\n";
    g << ans.size() << "\n";
    for (int i = 0; i < ans.size(); ++i)
        g << X[ans[i]] << " " << Y[ans[i]] << "\n";
}

int main()
{
    read();
    vsort();
    init();
    solve();
    show();
    return 0;
}