#include <bits/stdc++.h>
using namespace std;
ifstream fin ("kruskal.in");
ofstream fout ("kruskal.out");

int n, m;

struct dsu
{
    vector <int> p, sz;
    dsu()
    {
        p.resize(n + 1);
        sz.resize(n + 1);
        for (int i = 1; i <= n; i++)
        {
            p[i] = i;
            sz[i] = 1;
        }
    }

    int find_parent(int node)
    {
        if (p[node] == node)
            return node;
        return p[node] = find_parent(p[node]);
    }

    void unite(int x, int y)
    {
        x = find_parent(x);
        y = find_parent(y);
        if (sz[x] > sz[y])
            swap(x, y);
        p[x] = y;
        sz[y] += sz[x];
    }
};

int main()
{
    fin >> n >> m;

    dsu tree;
    vector <pair <int, pair<int, int> > > edg(m);

    for (int i = 1; i <= m; i++)
    {
        int cost, u, v;
        fin >> u >> v >> cost;
        edg[i - 1] = {cost, {u, v}};
    }
    sort(edg.begin(), edg.end());

    int ans = 0;
    vector <pair <int, int> > arb;
    for (int i = 0; i < m; i++)
    {
        int cost = edg[i].first;
        int u = edg[i].second.first;
        int v = edg[i].second.second;
        if (tree.find_parent(u) != tree.find_parent(v))
        {
            tree.unite(u, v);
            arb.push_back({u, v});
            ans += cost;
        }
    }

    fout << ans << '\n' << arb.size() << '\n';
    for (int i = 0; i < arb.size(); i++)
    {
        int u = arb[i].first, v = arb[i].second;
        fout << u << ' ' << v << '\n';
    }
}