#include <fstream>
#include <climits>
#include <bitset>
#include <vector>
#include <queue>
#define DIM 200011
#define INF INT_MAX
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m;
int D[DIM],E[DIM];

priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > h;
vector<pair<long long,int> > L[DIM];
bitset<DIM> viz;

int main(void){
    register int i,j,x,y,c,nod;
    long long val;
    pair<long long,int> p;
    vector<pair<long long,int> >::iterator it;

    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>c;
        L[x].push_back(make_pair(c,y));
        L[y].push_back(make_pair(c,x));
    }
    for(i=2;i<=n;i++) D[i]=INF;

    h.push(make_pair(0,1));
    while(!h.empty()){
        nod=h.top().second;
        val=h.top().first;
        h.pop();
        if(viz[nod])
            continue;
        for(it=L[nod].begin();it!=L[nod].end();it++){
            if(!viz[it->second] && D[it->second]>it->first){
                D[it->second]=it->first;
                E[it->second]=nod;
                h.push(make_pair(D[it->second],it->second));
            }
        }
        viz[nod]=1;
    }

    long long sol=0;
    for(i=1;i<=n;i++) sol+=D[i];
    g<<sol<<"\n"<<n-1<<"\n";
    for(i=2;i<=n;i++){
        g<<E[i]<<" "<<i<<"\n";
    }
    f.close();
    g.close();
    return 0;
}