#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int MAXN = 5010;
const int INF = 2e9;

int VEC[MAXN],ANS,V[MAXN],H[MAXN*2 + 100],POZ[MAXN];
vector<pair<int,int> > VECT[MAXN],VANS;
int N,M,L,C[MAXN];

void enter_apm(int x){
    for (auto it :VECT[x]){
        int nod = it.first;
        int cost = it.second;
        V[nod] = min(V[nod],cost);
        if (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[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 enter_heap(int nod){
    H[++L] = nod;
    POZ[nod] = L;
    pop(L);
}


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

void solve(){
    for (int i = 1; i <= N;i++) V[i] = INF;
    V[1] = 0;
    enter_apm(1);
    for (int i  = 2 ; i <= N;i++) enter_heap(i);
    for (int i = 1; i < N;i++){
        int x = get_root();
        enter_apm(x);
        ANS += V[x];
        VANS.push_back({x,VEC[x]});
        for (auto it:VECT[x]){
            int nod = it.first;
            if (POZ[nod]) pop(POZ[nod]);
        }
    }
    fout << ANS << "\n";
    fout << N - 1 << "\n";
    for (unsigned int i = 0; i < N - 1;i++) fout << VANS[i].first << " " << VANS[i].second<<"\n";


}

int main(){

    fin >> N >> M;
    for (int i = 1; i <= M;i++){
        int x,y,c;
        fin >> x >> y >> c;
        VECT[x].push_back({y,c});
        VECT[y].push_back({x,c});
    }

    solve();
    return 0;
}