#include <bits/stdc++.h>

using namespace std;

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

#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second

const int NMAX = 2e5 + 30;
const int INF = 0x3f3f3f3f;

int n, m, x, y, c, MSTwt, root[NMAX];
vector<tuple<int, int, int>> edges;
vector<pii> MST;

void read()
{
    in >> n >> m;
    while (m--)
        in >> x >> y >> c, edges.pb({c, x, y});
}

int getroot(int x)
{
    if (root[x] == x)
        return x;
    return (root[x] = getroot(root[x]));
}

void Kruskal()
{
    sort(edges.begin(), edges.end());

    for (int i = 1; i <= n; root[i] = i, i++)
        ;

    for (auto edge : edges)
    {
        tie(c, x, y) = edge;

        x = getroot(x);
        y = getroot(y);

        if (x != y) // not from the same tree
        {
            root[x] = y;
            MST.pb({x, y});
            MSTwt += c;
        }
    }
}

void solve()
{
    Kruskal();
    out << MSTwt << '\n'
        << MST.size() << '\n';
    for (auto edge : MST)
        out << edge.fi << ' ' << edge.se << '\n';
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);

    read();
    solve();

    return 0;
}