#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 200005
using namespace std;

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

struct edge
{
    int x, y, c;
};

vector <edge> E;
vector <int> G;
int n, m, C[NMAX], k;

int criteria(edge A, edge B)
{
    if(A.c > B.c)
        return 0;
    return 1;
}

int main()
{
    int i, j, a, b, cost;
    fin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        fin >> a >> b >> cost;
        edge p;
        p.x = a;
        p.y = b;
        p.c = cost;
        E.push_back(p);
    }
    for(i = 1; i <= n; i++)
        C[i] = i;
    sort(E.begin(), E.begin() + m, criteria);

    for(i = 0; i < E.size(); i++)
        fout << E[i].c << ' ';
    cost = 0;
    int min, max;
    while(G.size() < n - 1)
    {
        if(C[E[k].x] != C[E[k].y])
        {
            if(C[E[k].x] < C[E[k].y])
            {
                min = C[E[k].x];
                max = C[E[k].y];
            }
            else
            {
                max = C[E[k].x];
                min = C[E[k].y];
            }
            for(j = 1; j <= n; j++)
                if(C[j] == max)
                C[j] = min;
            cost += E[k].c;
            G.push_back(k);
        }
        ++k;
    }
    fout << cost << '\n';
    fout << n - 1 << '\n';
    for(i = 0; i < n - 1; i++)
        fout << E[G[i]].x << ' ' << E[G[i]].y << '\n';
    return 0;
}