#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX = 2e5;

struct edge{
    int x, y, c;

    bool operator < (const edge other) const
    {
        return c < other.c;
    }
};

int N, M;
int dad[NMAX + 5], rnk[NMAX + 5];

vector <edge> v;

long long apm;
vector <edge> apmEdges;

int root(int node)
{
    int initNode = node, d = dad[node];

    while(node != d)
    {
        node = d;
        d = dad[d];
    }

    dad[initNode] = d;
    return d;
}

void join(int p, int q)
{
    p = root(p);
    q = root(q);

    if(rnk[p] == rnk[q])
        rnk[p]++, dad[q] = p;
    else if(rnk[p] > rnk[q])
        dad[q] = p;
    else
        dad[p] = q;
}

int main()
{
    fin >> N >> M;

    for(int i = 1; i <= N; i++)
        dad[i] = i;

    for(int i = 1; i <= M; i++)
        {
            int x, y, c;
            fin >> x >> y >> c;
            v.push_back({x, y, c});
        }

    sort(v.begin(), v.end());

    for(int i = 0; apmEdges.size() < N - 1; i++)
    {
        edge currentEdge = v[i];

        if(root(currentEdge.x) != root(currentEdge.y))
            {
                join(currentEdge.x, currentEdge.y);

                apmEdges.push_back(currentEdge);
                apm += currentEdge.c;
            }
    }

    fout << apm << '\n' << apmEdges.size() << '\n';

    for(auto it : apmEdges)
        fout << it.x << ' ' << it.y << '\n';

    return 0;
}