#include<fstream>
#include<vector>
#include<set>
#include<bitset>

using namespace std;

const int nmax = 200005;

int t[nmax], d[nmax], n, m;
vector<pair<int, int> > gf[nmax];
multiset<pair<int, int> > s;
pair<int,int> apm[nmax];
bitset<nmax> viz;
int c_tot;


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

void citeste(){

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

}

void rezolva(){

    for(int i=1; i<=n; ++i) d[i] = 999999;

    d[1] = 0;
    viz[0]=1;

    s.insert(make_pair(0,1));

    for(; s.size(); ){
        int nod;
        for(nod = 0; viz[nod] && !s.empty(); nod = (*s.begin()).second, s.erase(*s.begin()));
        viz[nod] = 1;
        c_tot += d[nod];
        for(unsigned i=0; i < gf[nod].size(); ++i){
            int vecin = gf[nod][i].first;
            int cost = gf[nod][i].second;
            if (d[vecin] > cost && viz[vecin] == 0){
                d[vecin] = cost;
                t[vecin] = nod;
                s.insert(make_pair(d[vecin], vecin));
            }
        }
    }

}


void scrie(){

    g<<c_tot<<"\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;

}