#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 200100
#define INF 200000200

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie {
    int nodul,costul;
};
muchie BD(int n,int c) {//construire muchie
    muchie a;
    a.nodul=n;a.costul=c;
    return a;
}
vector<muchie> VECT[NMAX]; //muchii+cost
vector<muchie> VANS;// arbore partial
int VEC[NMAX],V[NMAX];//cel mai apropiat nod aflat deja in APM+costul spre acesta
int H[2*NMAX+200],POZ[NMAX];//heapul si pozitia in heap
int n,i,m,x,y,c,L,ANS;

void push_apm(int x) {
    for (int i=0;i<VECT[x].size();i++) {
        int nod=VECT[x][i].nodul;
        int cost=VECT[x][i].costul;
        if (cost<=V[nod]) V[nod]=cost,VEC[nod]=x;
    }
}
void push(int poz) {
    while((poz*2<=L && V[H[poz]]>V[H[poz*2]]) || (poz*2+1<=L && V[H[poz]]>V[H[poz*2+1]])) {
            if (V[H[poz*2]]<V[H[poz*2+1]] || poz*2+1>L) {
                swap(H[poz],H[2*poz]);
                swap(POZ[H[poz]],POZ[H[poz*2]]);
                poz*=2;
            }
            else {
                swap(H[poz],H[poz*2+1]);
                swap(POZ[H[poz]],POZ[H[poz*2+1]]);
                poz=poz*2+1;
            }
    }
}
void pop(int poz) {
    while (poz>1 && V[H[poz]]<V[H[poz/2]]) { //cat timp nu am ajuns in radacina si nodul curent e mai mic decat tatal
        swap(H[poz],H[poz/2]);//schimb nodul cu tatal
        swap(POZ[H[poz]],POZ[H[poz/2]]);//schimb pozitia nodului cu pozitia tatalui
        poz/=2;//merg in tata
    }
}
void push_heap(int x) {
    H[++L]=x;//introduc heap
    POZ[x]=L;//memorez pozitie
    pop(L);//rearanjez heap
}
int root_heap() {
    int x=H[1];
    swap(H[1],H[L]);//duc in varf ultimul element din heap
    swap(POZ[H[1]],POZ[H[L]]);
    L--;
    push(1);//rearanjez heap
    POZ[x]=0;
    return x;
}

int main () {
    f >> n >> m;
    for (i=1;i<=m;i++) {
        f >> x >> y >> c;
        VECT[x].push_back(BD(y,c));
        VECT[y].push_back(BD(x,c));
    }
    for (i=1;i<=n;i++) V[i]=INF;
    V[1]=0;
    push_apm(1);//introduc in APM un nod random (1)
    for (i=2;i<=n;i++)
        push_heap(i);//introduc in heap costuri minime ale noduri ce nu sunt in APM spre noduri ce sunt in APM
    for (i=1;i<n;i++) {// introduc in APM celelalte N-1 noduri
        x=root_heap();//iau nodul ce NU e in APM cu costul minim inspre APM
        push_apm(x);//introduc nodul in APM
        ANS+=V[x];//cresc costul final cu costul minim al noului nod spre APM
        VANS.push_back(BD(x,VEC[x]));//voi afisa muchia dintre nodul curent si cel mai apropiat din APM
        for (int j=0;j<VECT[x].size();j++) {//pentru toate muchiile ce pleaca din nodul curent
            int nod=VECT[x][j].nodul;//iau nodul corespondent
            if (POZ[nod]!=0) pop(POZ[nod]);//verific daca e in heap si actualizez heap-ul cu noile costuri minime
        }
    }
    g << ANS << '\n';//afisez costul minim al APM
    g << n-1 << '\n';
    for (i=0;i<n-1;i++)
        g << VANS[i].nodul << ' ' << VANS[i].costul << '\n';//afisezi muchiile APM-ului
    f.close();g.close();
    return 0;
}