#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int INF = 1e9;
const int NMAX = 10000;

int a[NMAX + 1][NMAX + 1], tata[NMAX + 1], n, m, cost;
bool viz[NMAX + 1];


void Prim(int nod_start)
{
    for(int i = 1; i <= n; i++)
    {
        tata[i] = nod_start;
    }
    viz[1] = 1;
    tata[nod_start] = 0;

    for(int k = 1; k < n; k++)
    {
        int min = INF, p = 0;
        for(int i = 1; i <= n; i++)
        {
            if(!viz[i] && a[i][tata[i]] < min)
            {
                min = a[i][tata[i]];
                p = i;
            }
        }
        viz[p] = 1;
        cost += min;
        cout << min << ' ';

        for(int i = 1; i <= n; i++)
        {
            if(!viz[i] && a[i][tata[i]] > a[i][p])
            {
                tata[i] = p;
            }
        }
    }

}

void afisare()
{
    fout << cost << '\n' << n-1 << '\n';
    for(int i = 2; i <= n; i++)
    {
        fout << i << ' ' << tata[i] << '\n';
    }
}

int main()
{
    int x, y, z;
    fin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1;j <= n; j++)
            if(i != j)
                a[i][j] = a[j][i] = INF;

    for(int j = 1; j <= m; j++)
    {
        fin >> x >> y >> z;
        a[x][y] = a[y][x] = z;

    }

    Prim(1);
    afisare();
}