#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX = 2e5 + 1;
int n, m, parent[NMAX], ans = 0;
struct edge{int u, v, cost;};
vector<edge> edges, tree;

bool cmp(edge A, edge B)
{
    return A.cost < B.cost;
}

int Find(int nod)
{
    if(parent[nod] < 0)
        return nod;
    return (parent[nod] = Find(parent[nod]));
}

bool Unire(int x, int y)
{
    int r1 = Find(x), r2 = Find(y);
    if(r1 == r2)
        return false;
    if(parent[r1] < parent[r2])
    {
        parent[r1] += parent[r2];
        parent[r2] = r1;
    }
    else
    {
        parent[r2] += parent[r1];
        parent[r1] = r2;
    }
    return true;
}

int main()
{
    fin >> n >> m;
    memset(parent, -1, sizeof(parent));
    while(m--)
    {
        int u, v, cost;
        fin >> u >> v >> cost;
        edges.push_back({u, v, cost});
    }
    sort(edges.begin(), edges.end(), cmp);

    for(auto edge : edges)
    {
        if(Unire(edge.u, edge.v))
        {
            ans += edge.cost;
            tree.push_back(edge);
        }
    }
    fout << ans << "\n" << tree.size() << "\n";
    for(auto edge : tree)
        fout << edge.u << " " << edge.v << "\n";

    return 0;
}