#include <fstream>
#include <iostream>
#include <vector>
#include <queue>

#define nmax 200005
#define x first
#define y second

using namespace std;

int n, m, t[nmax], d[nmax];
bool viz[nmax];
vector<pair<int,int> > gf[nmax];
int cost_minim = 0;

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

void citeste(){

    f >> n >> m;
    for(int i=1; i<=m; i++){
        int x, y, cost;
        f >> x >> y >> cost;
        gf[x].push_back(make_pair(y,cost));
        gf[y].push_back(make_pair(x,cost));
    }

}

struct cmp{

    bool operator () (pair<int,int> a, pair<int,int> b){

        return a.x > b.x;

    }

};

void rezolva(){

    priority_queue< pair<int,int>, vector<pair<int, int> > , cmp > Q;

    for(int i=1; i<=n; i++){
        d[i] = (1<<30);
        viz[i] = 0;
    }

    //aleg un nod
    d[1] = 0;

    //il bag in "heap"
    Q.push(make_pair(0,1));

    for( ;Q.size(); ){
        //cat timp minimul e folosit doar il scot din heap
        for(; Q.size(); ){
            int nod = (Q.top()).y;
            if (viz[nod] == 1) Q.pop();
            else break;
        }
        if (Q.size() == 0) break;
        int cost_nod = (Q.top()).x;
        int nod = (Q.top()).y;
        Q.pop();
        viz[nod] = 1;// marchez nodul ca vizitat
        cost_minim += cost_nod;

        for(int i=0; i<gf[nod].size(); i++){
            int vc = gf[nod][i].x;
            int cost = gf[nod][i].y;
            if ( d[vc] > cost ){//daca pot minimiza costul vecinului cu care se afla in Arbore il minimizez cu muchia nod-vecin
                d[vc] = cost;
                t[vc] = nod;
                Q.push(make_pair(d[vc], vc));
            }
        }
    }

}

void scrie(){

    g << cost_minim << "\n";
    g << n-1 << "\n";
    for(int i=2; i<=n; i++) g << t[i] << " " << i << "\n";

}


int main(){

    citeste();
    rezolva();
    scrie();

    f.close();
    g.close();

    return 0;

}