#include <bits/stdc++.h>
using namespace std;
int d[200005];
struct edge
{
    int x, y, c;
}v[200005];
vector <edge> edges;
bool cmp(edge a, edge b)
{
    return a.c < b.c;
}
int dad(int x)
{
    int y = x;
    while(x != d[x])
    {
        x = d[x];
    }
    while(y != x)
    {
        int aux = d[y];
        d[y] = x;
        y = aux;
    }
    return x;
}
int n, m, i, dad1, dad2, cost_total;
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    f >> n >> m;
    for(i = 1; i <= n; i ++)
        d[i] = i;
    for(i = 1; i <= m; i ++)
        f >> v[i].x >> v[i].y >> v[i].c;
    sort(v + 1, v + m + 1, cmp);
    for(i = 1; i <= m; i ++)
    {
        dad1 = dad(v[i].x);
        dad2 = dad(v[i].y);
        if(dad1 != dad2)
        {
            d[dad1] = dad2;
            edges.push_back(v[i]);
            cost_total = cost_total + v[i].c;
        }
    }
    g << cost_total << "\n";
    g << n - 1 << "\n";
    for(i = 0; i < edges.size(); i ++)
        g << edges[i].x << " " << edges[i].y << "\n";
    return 0;
}