#include <stdio.h>
#include <vector>
#include <algorithm>
#define nmax 200020
#define INF  200000200
#define in   "apm.in"
#define out  "apm.out"
using namespace std;


int N,M,L,allcost,B[nmax],VEC[nmax],POZ[nmax],H[2*nmax+100];
vector <pair<int,int> > G[nmax],TREE,peir;

void read()
     {freopen(in,"r",stdin);
      int i,a,b,c;scanf("%d %d\n",&N,&M);
      for(i=1;i<=M;i++)
              {scanf("%d %d %d\n",&a,&b,&c);
               G[a].push_back(make_pair(b,c));
               G[b].push_back(make_pair(a,c));
              }
      fclose(stdin);
      }
void load_in_apm(int nod)
     {int k,c,boy;
      for(k=0;k<G[nod].size();k++)
          {boy=G[nod][k].first;
           c=G[nod][k].second;
           B[boy]=min(B[boy],c);
           if(B[boy]==c)    VEC[boy]=nod;
           }
      }
void push(int poz)
     {while((poz * 2 <= L && B[H[poz]] > B[H[poz * 2]]) || (poz * 2 + 1 <= L && B[H[poz]] > B[H[poz * 2 + 1]]))
	   {if (B[H[poz * 2]] < B[H[poz * 2 + 1]] || poz * 2 + 1 > L)			
		   {swap(H[poz],H[poz * 2]);
		    swap(POZ[H[poz]],POZ[H[poz * 2]]);
		    poz *= 2;
	       }
		else 
		   {swap(H[poz],H[poz * 2 + 1]);
            swap(POZ[H[poz]],POZ[H[poz * 2 + 1]]);
			poz = poz * 2 + 1;
           }
       } 
     }
void pop(int poz)
     {while(poz > 1 && B[H[poz]] < B[H[poz / 2]])
	    {swap(H[poz],H[poz / 2]);
		swap(POZ[H[poz]],POZ[H[poz / 2]]);
		poz = poz / 2;
	    }
     } 
void load_in_heap(int nod)
     {H[++L]=nod;
      POZ[nod]=L;
      pop(L);
     }
int get_out_root()
{
	int x = H[1];
	H[1]=H[L];
	POZ[H[1]]=1;
	L--;push(1);POZ[x] = 0;
	return x;
}
void createamp()
     {int i,j,x,kid;B[1]=0;
      for(i=2;i<=N;i++)     B[i]=INF;
      load_in_apm(1);
      for(i=2;i<=N;i++)     load_in_heap(i);
      for(i=1;i<N;i++)
                {x=get_out_root();
                 load_in_apm(x);
                 allcost+=B[x];
                 TREE.push_back(make_pair(x,VEC[x]));
                 for(j=0;j<G[x].size();j++)
                         {kid=G[x][j].first;
                          if(POZ[kid])     pop(POZ[kid]);
                          }
                }
      }
void write()
     {freopen(out,"w",stdout);
      int i,j;
      printf("%d\n%d\n",allcost,N-1);
      for(j=0;j<TREE.size();j++)
                   printf("%d %d\n",TREE[j].first,TREE[j].second);
      fclose(stdout);     
      }
int main()
    {read();
     createamp();
     write();
     return 0;
     }