#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX = 200005;
const int infinit = (1<<30);

int VEC[NMAX],ANS,V[NMAX],H[NMAX*2],POZ[NMAX];
vector <pair<int,int> > Muchii[NMAX],VANS;
int N,M,L,C[NMAX];

void DFS(int Nod) {
    for(unsigned i=0; i<Muchii[Nod].size(); ++i) {
        int vecin=Muchii[Nod][i].first;
        int cost=Muchii[Nod][i].second;
        V[vecin]=min(V[vecin],cost);
        if(V[vecin]==cost) VEC[vecin]=Nod;
    }
}

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[poz*2]);
            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]]) {
        swap(H[poz],H[poz/2]);
        swap(POZ[H[poz]],POZ[H[poz/2]]);
        poz/=2;
    }
}

void Heap(int Nod) {
    H[++L]=Nod;
    POZ[Nod]=L;
    pop(L);
}

int SHeap() {
    int x = H[1];
    swap(H[1],H[L]);
    swap(POZ[H[1]],POZ[H[L]]);
    L--;
    push(1);
        POZ[x] = 0;
    return x;
}

int main()
{
    fin>>N>>M;
    for(int i=1; i<=M; ++i) {
        int x,y,c;
        fin>>x>>y>>c;
        Muchii[x].push_back(make_pair(y,c));
        Muchii[y].push_back(make_pair(x,c));
    }
    for(int i=1; i<=N; ++i) V[i]=infinit;
    V[1]=0;
    DFS(1);
    for(int i=2; i<=N; ++i) Heap(i);
    for(int i=1; i<N; ++i) {
        int x = SHeap();
        DFS(x);
        ANS+=V[x];
        VANS.push_back(make_pair(x,VEC[x]));
        for(unsigned j=0; j<Muchii[x].size(); ++j) {
            int nod = Muchii[x][j].first;
            if (POZ[nod]) pop(POZ[nod]);
        }
    }
    fout<<ANS<<endl;;
    fout<<N-1<<endl;
    for(unsigned i = 0;i < N - 1; ++i)
        fout<<VANS[i].first<<' '<<VANS[i].second<<endl;
    return 0;
}