#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream ka("apm.in");
ofstream ki("apm.out");

const int N_MAX = 200000;
const int M_MAX = 400000;
struct varf
{
    int index;
    int cost;
    bool operator < (const varf arg) const
    {
        return cost > arg.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];

priority_queue <varf> coada;

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])
                coada.push(graf[curent][i]);
        varf v = coada.top();
        coada.pop();
        while(este[v.index])
        {
            v = coada.top();
            coada.pop();
        }
        sol[++sol[0]] = v.index;
        sol[++sol[0]] = curent;
        curent = v.index;
        suma += v.cost;
        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';
}