#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#define NMAX 1001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int tata[NMAX];
int h[NMAX];
int N,M;
double costmin;
struct Muchie
{
    int x,y;
    double cost;
    friend bool operator > (const Muchie&, const Muchie&);
};
vector< Muchie > sol;
bool operator > (const Muchie& m1, const Muchie& m2)
{
    return m1.cost > m2.cost;
}
priority_queue< Muchie, vector < Muchie>, greater<Muchie> >H;
void citire()
{
    Muchie m;
    fin>>N>>M;
    for(int i = 1; i <= M ; i++)
    {
        fin>>m.x>>m.y>>m.cost;
        H.push(m);
    }
}
int Find(int x)
{
    int r=x;
    while(tata[x]) r=tata[r];
    int y=x,aux;
    while(y!=r)
    {
        aux=tata[y];
        tata[y]=r;
        y=aux;
    }
    return r;
}
int Union(int c1, int c2)
{
    if(h[c1] > h[c2]) tata[c2]=c1;
    else
    {
        tata[c1]=c2;
        if(h[c1]==h[c2]) h[c2]++;
    }
}
void afisare()
{
    fout<<costmin<<'\n';
    for(int i = 0 ; i < N-1 ; i++)
        fout<<sol[i].x<<" "<<sol[i].y;
}
int main()
{
    int c1,c2;
    Muchie m;
    citire();
    while(sol.size() < N - 1)
    {
        m=H.top();
        H.pop();
        c1=Find(m.x);
        c2=Find(m.y);
        if(c1!=c2)
        {
            costmin+=m.cost;
            sol.push_back(m);
            Union(c1,c2);
        }

    }
    afisare();
    return 0;
}