#include <fstream>
#include<algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

const int maxn = 200502;
const int inf = 200000200;

int VEC[maxn],Suma,dist[maxn],Heap[maxn * 2 + 100],Pozitie[maxn];
struct vect { int x,cost; vect *urm;};
vect *a[maxn];
vect *Rez;
int n,m,x,y,c,ElementeHeap;

void introduce_in_apm(int x)
{
    vect *aux = a[x];
    int nod,cost;
    while(aux)
    {
        nod = aux->x;
        cost = aux->cost;
        dist[nod] = min(dist[nod],cost);
        if (dist[nod] == cost) VEC[nod] = x;
        aux=aux->urm;
    }
}

void RearanjareHeap()
{
    int NodStart = 1, fiu, aux;
    while(NodStart < ElementeHeap)
    {
        fiu = NodStart << 1;
        if(fiu <= ElementeHeap)
        {
            if(fiu+1 <= ElementeHeap && dist[Heap[fiu]] > dist[Heap[fiu+1]]) fiu++;
            if(dist[Heap[fiu]] < dist[Heap[NodStart]])
            {
                Pozitie[Heap[fiu]] = NodStart;
                Pozitie[Heap[NodStart]] = fiu;
                aux = Heap[fiu], Heap[fiu] = Heap[NodStart], Heap[NodStart] = aux;
                NodStart = fiu;
            }
            else return;
        }
        else return;
    }
}


void AddHeap(int ElemCurent)
{
    int tata;
    while(ElemCurent > 1)
    {
        tata = ElemCurent>>1;
        if(dist[Heap[ElemCurent]] < dist[Heap[tata]])
        {
            swap(Heap[ElemCurent],Heap[tata]);
            swap(Pozitie[Heap[ElemCurent]],Pozitie[Heap[tata]]);
            ElemCurent = tata;
        }
        else return;
    }
}

void introduce_in_heap(int nod)
{
    Heap[++ElementeHeap] = nod;
    Pozitie[nod] = ElementeHeap;
    AddHeap(ElementeHeap);
}

int scoate_radacina_heap()
{
    int x = Heap[1];
    swap(Heap[1],Heap[ElementeHeap]);
    swap(Pozitie[Heap[1]],Pozitie[Heap[ElementeHeap]]);
    ElementeHeap--;
    RearanjareHeap();
    Pozitie[x] = 0;
    return x;
}

void Adauga(int x, int y, int c)
{
    vect *aux = new vect;
    aux->x = y;
    aux->cost = c;
    aux->urm = a[x];
    a[x]=aux;
}

int main()
{
    cin>>n>>m;
    for(int i = 1;i <= m;i++) cin>>x>>y>>c,Adauga(x,y,c),Adauga(y,x,c);
    for(int i = 2;i <= n;i++) dist[i] = inf;
    introduce_in_apm(1);
    for(int i = 2;i <= n;i++) introduce_in_heap(i);
    for(int i = 1;i < n;i++)
    {
        x = scoate_radacina_heap();
        introduce_in_apm(x);

        Suma += dist[x];

        vect *aux = new vect;
        aux->x=x,aux->cost = VEC[x],aux->urm = Rez, Rez = aux;

        aux = a[x];
        while(aux) {if (Pozitie[aux->x]) AddHeap(Pozitie[aux->x]); aux=aux->urm;}
    }
    cout<<Suma<<'\n';
    cout<<n-1<<'\n';
    while(Rez) cout<<Rez->x<<' '<<Rez->cost<<'\n',Rez = Rez->urm;
}