#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200000 + 1;
const int MAX_M = 400000 + 1;

struct Edge
{
    int x, y, c;

    bool operator < (const Edge &E) const
    {
        return this->c < E.c;
    }
};

Edge edges[MAX_M];
int M;

int father[MAX_N], ranks[MAX_N];
int N;

int root(int x)
{
    int y = x;

    while (y != father[y])
        y = father[y];

    while (x != father[x])
    {
        int tmp = father[x];
        father[x] = y;
        x = tmp;
    }

    return y;
}

void Union(int x, int y)
{
    if (ranks[x] > ranks[y])
        father[y] = x;
    else
        father[x] = y;

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

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

    in >> N >> M;

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

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

    for (int i = 1; i <= N; ++i)
    {
        father[i] = i;
        ranks[i] = 1;
    }

    int costTotal = 0;
    int nrEdges = 0;

    vector<int> inds;

    for (int i = 1; i <= M && nrEdges < N - 1; ++i)
    {
        int x = edges[i].x;
        int y = edges[i].y;

        x = root(x);
        y = root(y);

        if (x != y)
        {
            costTotal += edges[i].c;
            nrEdges++;
            inds.push_back(i);

            Union(x, y);
        }
    }

    out << costTotal << "\n";
    out << nrEdges << "\n";

    for (auto it : inds)
        out << edges[it].x << " " << edges[it].y << "\n";


    return 0;
}