#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX = 200000;
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 > edges;
vector < Edge > apmEdges;
int root(int node)
{
    if(node == dad[node])
        return node;
    return dad[node] = root(dad[node]);
}
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 from, to, cost; fin >> from >> to >> cost;
        edges.push_back({from, to, cost});
    }
    sort(edges.begin(), edges.end());
    long long APM = 0;
    for(auto it : edges)
        if(root(it.x) != root(it.y))
        {
            join(it.x, it.y);
            APM += it.c;
            apmEdges.push_back(it);
        }
    fout << APM << '\n' << N - 1 << '\n';
    for(auto it : apmEdges)
        fout << it.x << ' ' << it.y << '\n';
    return 0;
}