#include <fstream>
#include <vector>

using namespace std;
ifstream ka("apm.in");
ofstream ki("apm.out");

const int N_MAX = 500;
const int M_MAX = N_MAX * N_MAX;
struct varf
{
    int index;
    int cost;
};

int n, m, minimul = 0x7fffffff;
vector< vector <varf> >graf(N_MAX + 1);
int candidati[N_MAX + 1], cost[N_MAX + 1];
bool este[N_MAX + 1];

int sol[2 * N_MAX + 1];

int prim()
{
    int suma = 0;
    int curent = 1;
    int total = 1;
    for(int i = 1; i <= n; i++)
        candidati[i] = 0x7fffffff;
    while(total < n)
    {
        este[curent] = 1;
        for(int i = 0; i < graf[curent].size(); i++)
            if(graf[curent][i].cost < candidati[graf[curent][i].index] && !este[graf[curent][i].index])
                candidati[graf[curent][i].index] = graf[curent][i].cost;
        int minim = 0x7fffffff, poz;
        for(int i = 1; i <= n; i++)
            if(!este[i] && candidati[i] < minim)
            {
                poz = i;
                minim = candidati[i];
            }
        sol[++sol[0]] = curent;
        sol[++sol[0]] = poz;
        curent = poz;
        suma += minim;
        total++;
    }
    return suma;
}

int main()
{
    ka >> n >> m;
    int x, y, z;
    for(int i = 1; i <= m; i++)
    {
        ka >> x >> y >> z;
        varf v;
        v.index = y;
        v.cost = z;
        graf[x].push_back(v);
        v.index = x;
        graf[y].push_back(v);
    }
    int raspuns = prim();
        ki << raspuns << '\n' << sol[0] / 2 << '\n';
    for(int i = 1; i <= sol[0]; i += 2)
        ki << sol[i] << " " << sol[i+1] << '\n';
}