#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct edge {
    bool friend operator<(const edge& e1, const edge& e2)
    {
        return e1.cost < e2.cost;
    }
    int n1, n2;
    long long cost;
};

vector<edge> edges;
int n;
const int maxn = 200100;

struct DSU {
    vector<int> comp, sz;

    void initialize (int n)
    {
        comp.resize(n + 1);
        sz.resize(n + 1, 1);
        for (int i = 1; i <= n; i++)
        {
            comp[i] = i;
        }
    }

    int find (int x)
    {
        if (comp[x] == x) return x;
        else return x = find(comp[x]);
    }

    void unite(int x, int y)
    {
        x = comp[x], y = comp[y];
        if (sz[x] < sz[y]) swap(x, y);
        if (x == y) return;
        comp[y] = x;
        sz[x] += sz[y];
    }
};

vector<int> mst[maxn];

long long kruskal ()
{
    long long cost = 0;
    DSU dsu;
    dsu.initialize(n);
    sort(edges.begin(), edges.end());

    for (auto edge : edges)
    {
        if (dsu.find(edge.n1) != dsu.find(edge.n2))
        {
            mst[edge.n1].push_back(edge.n2);
            mst[edge.n2].push_back(edge.n1);
            dsu.unite(edge.n1, edge.n2);
            cost += edge.cost;
        }
    }
    return cost;
}

int main ()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int m; cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c; cin >> x >> y >> c;
        edges.push_back({x, y, c});
    }
    cout << kruskal() << '\n';
    cout << n - 1 << '\n';
    for (int i = 1; i <= n; i++)
    {
        for (auto to : mst[i])
        {
            if (to > i) cout << i << ' ' << to << '\n';
        }
    }
}