// 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;

class cmp
{
public:
    bool operator()(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 <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);
        V.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){
        priority_queue <pair <int, int>, vector <pair <int, int> >, cmp > Q; //first = nod, second = valoare cheie
        int i, sum, ramas;
        pair <int, int> u;
        list <pair <int, int> >::iterator parc;
        //Initializam heap-ul de chei + vector de chei
        for(i=1; i<=N; i++){
            cheie[i] = 1001;
        }
        //Initializam radacina cu 0 la parinte si distanta
        p[r]=0;
        cheie[r]=0;
        ramas = N; //numarul de noduri ramase
        Q.push(make_pair(r, 0) );
        while(!Q.empty() && ramas>0){
            //Cat timp exista noduri in pq
            u=Q.top();
            while(vis[u.first]==1){
                //Daca deja a fost vizitat, ii dam pop si trecem la urmatorul
                Q.pop();
                u=Q.top();
            }
            //Dupa ce ajungem la unul nevizitat, ii dam pop din Q
            Q.pop();
            parc = V[u.first].begin();
            vis[u.first]=1;
            //Verificam muchiile nodului curent, si modificam costurile dupa cum este necesar
            while(parc != V[u.first].end()){
                //Daca nodul a fost vizitat, il stergem din lista de muchii
                if(vis[(*parc).first]==1){
                    V[u.first].erase(parc++);
                }else{
                    if((*parc).second < cheie[(*parc).first] ){
                        //Daca aceasta muchie are un cost mai mic, modificam si adaugam aceasta muchie in pq
                        p[(*parc).first]=u.first;
                        cheie[(*parc).first]=(*parc).second;
                        Q.push(make_pair((*parc).first, (*parc).second) );
                    }
                    parc++;
                }
            }
            ramas--;
        }
        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;
}