#include <stdio.h>
#include <vector>
#include <set>
#define Nmax 200002
#define Mmax 400002
#define pb push_back
#define mp make_pair
#define y first
#define c second
#define INF 2147000000

using namespace std;
set< pair<int,int> > Set;
vector< pair<int,int> > v[Nmax];
int TT[Nmax],cmin[Nmax],use[Nmax];
int X[Mmax],Y[Mmax];
int N,M;

int main(){
    vector< pair<int,int> >:: iterator it;
    set< pair< int,int > >:: iterator pset;
    int i,cost=0,pmin,x,y,z;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(i=1;i<=M;++i){
        scanf("%d%d%d",&x,&y,&z);
        v[x].pb(mp(y,z));
        v[y].pb(mp(x,z));
    }

    for(i=2;i<=N;++i) cmin[i]=INF;
    for(it=v[1].begin(); it!=v[1].end(); ++it){
        Set.insert(mp(it->c,it->y));
        cmin[it->y]=it->c;
        TT[it->y]=1;
    }

    use[1]=1;
    for(i=2; i<=N; ++i){
        cost += Set.begin()->first;
        pmin=Set.begin()->second;
        use[pmin]=1;
        Set.erase(Set.begin());
        X[++X[0]]=TT[pmin]; Y[++Y[0]]=pmin;

        for(it=v[pmin].begin(); it!=v[pmin].end(); ++it)
            if( cmin[it->y] > it->c && !use[it->y]){
                pset=Set.find(mp(cmin[it->y],it->y));
                if( pset!=Set.end() ) Set.erase(pset);
                cmin[it->y]=it->c;
                Set.insert(mp(it->c,it->y));
                TT[it->y]=pmin;
            }
    }

    printf("%d\n%d\n",cost,N-1);
    for(i=1;i<=X[0];++i) printf("%d %d\n",X[i],Y[i]);
    fclose(stdin); fclose(stdout);
    return 0;
}