#include <bits/stdc++.h>

using namespace std;

constexpr int MAX_N = 200000;
constexpr int MAX_M = 400000;

struct Edge
{
    int x, y, c;

    bool operator < (const Edge &e) const
    {
        return c < e.c;
    }
};

struct DSU
{
    int tata[MAX_N + 1];
    int rank[MAX_N + 1];

    void initialize(int N)
    {
        for (int i = 1; i <= N; ++i)
        {
            tata[i] = i;
            rank[i] = 1;
        }
    }

    int findRoot(int x)
    {
        if (x != tata[x])
            return tata[x] = findRoot(tata[x]);
        else
            return x;
    }

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

        if (x != y)
        {
            if (rank[y] < rank[x])
                swap(x, y);

            tata[x] = y;

            if (rank[x] == rank[y])
                rank[y]++;
        }
    }
};

int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");

    int N, M;
    vector<Edge> edges;
    vector<bool> used;

    in >> N >> M;

    edges.resize(M);
    used.resize(M);

    for (int i = 0; i < M; ++i)
    {
        in >> edges[i].x;
        in >> edges[i].y;
        in >> edges[i].c;
    }

    DSU dsu;
    dsu.initialize(N);

    sort(edges.begin(), edges.end());
    long long totalSum = 0;

    for (int i = 0; i < M; ++i)
    {
        int x = edges[i].x;
        int y = edges[i].y;

        if (dsu.findRoot(x) != dsu.findRoot(y))
        {
            totalSum += edges[i].c;
            dsu.unite(x, y);
            used[i] = true;
        }
    }

    out << totalSum << endl;
    out << N - 1 << endl;

    for (int i = 0; i < M; ++i)
        if (used[i])
            out << edges[i].x << " " << edges[i].y << "\n";

    return 0;
}