#include<cstdio>
#include<set>
#include<vector>
#define dmax 2000000000
using namespace std;
vector< pair<int,int> >L[200100];
vector< pair<int,int> >::iterator it;
set< pair<int,int> >s;
set< pair<int,int> >::iterator itt;
int n,m,i,j,d[200100],v[200100],l[400100],C[400100],t[400100],sum,nr,a,b,c,ok,vmin,poz;
FILE *f,*g;
int main(){
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(f,"%d%d%d",&a,&b,&c);
        L[a].push_back(make_pair(b,c));
        L[b].push_back(make_pair(a,c));
    }
    for(i=2;i<=n;i++){
        d[i]=dmax;
        s.insert(make_pair(dmax,i));
    }
    d[1]=0;
    s.insert(make_pair(0,1));
    while(!ok&&!s.empty()){
        itt=s.begin();
        vmin=itt->first;
        if(vmin==dmax)
            break;
        poz=itt->second;
        sum+=vmin;
        l[++nr]=t[poz];
        C[nr]=poz;
        v[poz]=1;
        s.erase(itt);
        for(it=L[poz].begin();it!=L[poz].end();it++){
            if(d[it->first]>it->second&&v[it->first]==0){
                s.erase(s.find(make_pair(d[it->first],it->first)));
                d[it->first]=it->second;
                s.insert(make_pair(d[it->first],it->first));
                t[it->first]=poz;
            }
        }
    }
    fprintf(g,"%d\n%d\n",sum,nr-1);
    for(i=2;i<=nr;i++){
        fprintf(g,"%d %d\n",l[i],C[i]);
    }


    fclose(f);
    fclose(g);
    return 0;
}