#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
using namespace std;

typedef vector < pair<int,int> > vii;
#define INF 0x7f7f7f7f
#define to first
#define we second
#define MINP 1
#define le(K) (K<<1)
#define ri(K) ((K<<1) + 1)
#define fa(K) (K >> 1)

const int NMAX = 200000;
int N,M,apm[NMAX],capm,H[NMAX+1],HSZ,pos[NMAX],cmin[NMAX];
bool intree[NMAX];
vii G[NMAX];

void readGraph() {
     
     freopen("apm.in","r",stdin);
     scanf("%d%d",&N,&M);
     
     int x,y,w,i=0;
     for(;i<M;++i) {
                     
             scanf("%d%d%d",&x,&y,&w);
             G[--x].push_back(make_pair(--y,w));
             G[y].push_back(make_pair(x,w));
             }    
     }

void hswap(int x,int y) {
     pos[H[x]] = y; pos[H[y]] = x;
     int aux = H[x]; H[x] = H[y]; H[y] = aux;
     }

void lift(int K) {
     
     for(; K > 1 && cmin[H[K]] < cmin[H[fa(K)]] ; K = fa(K) )
           hswap(K,fa(K));
     }

void dip(int K) {
     
     int p;
     for(; ; K = p) {
              
              p = K;
              if(le(K) <= HSZ && cmin[H[le(K)]] < cmin[H[p]])
                       p = le(K);
              if(ri(K) <= HSZ && cmin[H[ri(K)]] < cmin[H[p]])
                       p = ri(K);
              
              if(p != K) hswap(p,K);
                   else break;
              }
     }

inline int hget(int K) {
       return H[K];
       }

int herase(int K) {
    int sav = H[K];
    hswap(K,HSZ--);
    dip(K);
    return sav;
}

void hinsert(int v,int c) {
     
     H[++HSZ] = v; pos[v] = HSZ; cmin[v] = c;
     lift(HSZ);
     }
     
void hupdate(int K,int c) {
     
     cmin[H[K]] = c;
     if(K > 1 && cmin[H[K]] < cmin[H[fa(K)]]) 
       lift(K);
      else dip(K);
     }

void prim() {

     int vmin = -1;
     memset(cmin,0x7f,sizeof cmin);
     cmin[0] = 0;
     
     hinsert(0,0);
          
     for(int e=0;e<N;++e) {
             
             vmin = herase(MINP);
             intree[vmin] = true; //for(int i=0;i <N;++i) printf("%d cu costul %d\n",i,cmin[i]); printf("\n");
             capm += cmin[vmin];
             
             for(vii :: iterator it = G[vmin].begin(); it != G[vmin].end(); ++it)
                    
                     if(!intree[it->to] && it->we < cmin[it->to]) {
                       if(cmin[it->to] == INF) hinsert(it->to,it->we);
                         else hupdate(pos[it->to],it->we);
                       apm[it->to] = vmin;                       
                     }
             }
}
     
void writeTree() {
     
     freopen("apm.out","w",stdout);
     printf("%d\n%d\n",capm,N-1);
     for(int i=1;i<N;++i)
             printf("%d %d\n",apm[i]+1,i+1); //se putea fol un vector pt afisarea in ordinea gasirii
     }
int main() { 
    readGraph();
    prim();
    writeTree();
}