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

struct DSU{
    vector<int> p, sz;

    DSU() {}

    DSU(int n)
    {
        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 x)
    {
        if (p[x] == x)
            return x;

        p[x] = find_parent(p[x]);
        return p[x];
    }

    void unite(int x, int y)
    {
        x = find_parent(x);
        y = find_parent(y);

        if (x == y)
            return;

        if (sz[x] > sz[y])
            swap(x, y);

        p[x] = y;
        sz[y] += sz[x];
    }
};

DSU dsu;

int n, m;

struct edge{
    int a, b, cost;
    edge(int x, int y, int c)
    {
        a = x;
        b = y;
        cost = c;
    }
    edge() {}

    bool operator < (const edge &o) const {return cost < o.cost;}
};

edge edges[400005];

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = edge(a, b, c);
    }

    sort(edges + 1, edges + m + 1);

    dsu = DSU(n);

    vector<edge> answer;
    answer.reserve(n - 1);

    int sum = 0;

    int i = 1;

    while (answer.size() < n - 1)
    {
        if (dsu.find_parent(edges[i].a) != dsu.find_parent(edges[i].b))
        {
            dsu.unite(edges[i].a, edges[i].b);
            answer.push_back(edges[i]);
            sum += edges[i].cost;
        }
        ++i;
    }

    cout << sum << '\n';
    cout << n - 1 << '\n';

    for (auto &e : answer)
        cout << e.a << ' ' << e.b << '\n';
}