// http://www.infoarena.ro/problema/apm
// Rezolvat prin Prim

//-1 000 <= C <= 1 000
//Infinit = 1001
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
using namespace std;

int cmp(pair <int, int> st, pair <int, int> dr)
{
    return st.second < dr.second;
}

class graf
{
private:
    /*
    N = nr. noduri
    M = nr. muchii
    p = vector costuri
    V = lista de adiacenta V[muchie_1] = makepair(muchie_2, cost)
    V2 = arborele de cost minim
    Q = vectorul de chei
    vis = lista de noduri vizitate
    */
    int N, M;
    vector <int> p, cheie;
    vector <list <pair <int, int> > > V;
    vector <pair <int, int> > Q; //first = nod, second = valoare cheie
    vector <int> vis;
public:
    graf(){
        ifstream f("apm.in");
        //Citim numarul de noduri si muchii
        f>>N>>M;
        //Initializam dimensiunile vectorilor
        V.resize(N+1);
        p.resize(N+1);
        cheie.resize(N+1);
        vis.resize(N+1);
        int i, aux1, aux2, aux3;
        //Citim matricea si inseram nodurile in lista de adiacenta
        for(i=0; i<M; i++){
            f>>aux1>>aux2>>aux3;
            V[aux1].push_back(make_pair(aux2, aux3) );
            V[aux2].push_back(make_pair(aux1, aux3) );
        }
        f.close();
    }

    void prim(int r){
        int i, sum;
        pair <int, int> u;
        list <pair <int, int> >::iterator parc;
        //Initializam heap-ul de chei + vector de chei
        for(i=1; i<=N; i++){
            Q.push_back(make_pair(i, 1001));
            cheie[i] = 1001;
        }
        //Initializam radacina cu 0 la parinte si distanta
        p[r]=0;
        cheie[r]=0;
        Q[r-1].second = 0;
        make_heap(Q.begin(), Q.end(), cmp);
        while(!Q.empty()){
            sort_heap(Q.begin(), Q.end(), cmp);
            u=Q.front();
            pop_heap(Q.begin(), Q.end(), cmp);
            Q.pop_back();
            parc = V[u.first].begin();
            while(parc != V[u.first].end()){
                if(vis[(*parc).first]==0 && (*parc).second < cheie[(*parc).first] ){
                    p[(*parc).first]=u.first;
                    cheie[(*parc).first]=(*parc).second;
                    for(i=0; i<Q.size(); i++){
                        if(Q[i].first == (*parc).first){
                            if((*parc).second < Q[i].second){
                                Q[i].second = (*parc).second;
                            }
                            break;
                        }
                    }
                }
                parc++;
            }
            vis[u.first]=1;
        }
        sum=0;
        for(i=1; i<=N; i++)
            sum+=cheie[i];
        ofstream g("apm.out");
        g<<sum<<endl<<N-1<<endl;
        for(i=2; i<=N; i++)
            g<<i<<" "<<p[i]<<endl;
    }

};

int main()
{
    graf V;
    V.prim(1);
    return 0;
}