#include <iostream>
#include <vector>
#define INF 0x3f3f3f3
#define pb push_back
#define mp make_pair
#define cost second
#define nod first 
using namespace std;
vector < pair<int,int> > V[100013],Sol;
int n,m,i,a,b,c,length(0),v,f(0),k;
int H[100013],D[100013],viz[1000013],source[100013],poz[100013],s(0);

void heap_down(int nod)
{
  int fiu(1);
  do {
      fiu=0;
      if (nod*2<=length){
                    fiu=nod*2;
                    if(nod*2<length && D[H[nod*2+1]]<D[H[nod*2]]) fiu=nod*2+1;
                    if (D[H[fiu]]>=D[H[nod]]) fiu=0;
                    }
      if (fiu){
               swap(poz[H[nod]],poz[H[fiu]]);
               swap(H[nod],H[fiu]);
               nod=fiu;
              }
      }
  while(fiu);
}
void heap_up(int k)
{
 
}

int main()
{
 freopen("apm.in","r",stdin);
 freopen("apm.out","w",stdout); 
 cin>>n>>m;
 while(m--){
            cin>>a>>b>>c;
            V[a].pb(mp(b,c));
            V[b].pb(mp(a,c));
            }
 for (i=2;i<=n;++i) D[i]=INF;
 H[1]=length=viz[1]=poz[1]=1;    
 while(length){
               v=H[1];
               Sol.pb(mp(v,source[v]));
               ++f;
               s+=D[v];
               poz[H[length]]=poz[H[1]];
               H[1]=H[length];
               --length;
               heap_down(1);
               for (i=0;i<V[v].size();++i)
                  {
                   if (viz[V[v][i].nod]==0){
                                           H[++length]=V[v][i].nod;
                                           viz[V[v][i].nod]=1;
                                           poz[H[length]]=length;
                                           }
                   if (V[v][i].cost<D[V[v][i].nod]){
                                                    D[V[v][i].nod]=V[v][i].cost;
                                                    source[V[v][i].nod]=v;
                                                    k=poz[V[v][i].nod];
                                                    while(k>1 && D[H[k]]<D[H[k/2]]){
                                                       swap(poz[H[k]],poz[H[k/2]]);
                                                       swap(H[k],H[k/2]);
                                                       k/=2;
                                                                       }                  
                                 }
                   }
             }           
 cout<<s<<"\n";
 cout<<f-1<<"\n";
 for (i=1;i<Sol.size();++i) cout<<Sol[i].first<<" "<<Sol[i].second<<"\n";           
 return 0;
}