// Arbore partial de cost minim

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN=200010;
const int INF=2000000200;
int n,m,l,suma,v[MAXN],H[MAXN*2+10],POZ[MAXN],vec[MAXN];
vector <pair<int,int> > vecini[MAXN],sol;

void introduce_in_apm(int x)
{
     int i,nod,cost;
     for(i=0;i<vecini[x].size();i++)
     {
      nod=vecini[x][i].first;
      cost=vecini[x][i].second;
      v[nod]=min(v[nod],cost);
      if(v[nod]==cost) vec[nod]=x;
     }
}

void push(int poz)
{
     while((poz*2<=l && v[H[poz]]>v[H[poz*2]]) || (poz*2+1<=l && v[H[poz]]>v[H[poz*2+1]]))
     {
      if(v[H[poz*2]]<v[H[poz*2+1]]||poz*2+1>l)
      {
       swap(H[poz],H[poz*2]);
       swap(POZ[H[poz]],POZ[H[poz*2]]);
       poz=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 && v[H[poz]]<v[H[poz/2]])
     {
                 swap(H[poz],H[poz/2]);
                 swap(POZ[H[poz]],POZ[H[poz/2]]);
                 poz=poz/2;
     }
}

void introduce_in_heap(int nod)
{
     H[++l]=nod;
     POZ[nod]=l;
     pop(l);
}

int scoate_radacina_heap()
{
    int x;
    x=H[1];
    H[1]=H[l];
    l--;
    push(1);
    POZ[x]=0;
    return x;
}

int main()
{
    int i,j,x,y,c,nod;
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
     f>>x>>y>>c;
     vecini[x].push_back(make_pair(y,c));
     vecini[y].push_back(make_pair(x,c));
    }
    for(i=1;i<=n;i++) v[i]=INF;
    v[1]=0;
    introduce_in_apm(1);
    for(i=2;i<=n;i++)
     introduce_in_heap(i);
    for(i=1;i<n;i++)
    {
     x=scoate_radacina_heap();
     introduce_in_apm(x);
     suma+=v[x];
     sol.push_back(make_pair(x,vec[x]));
     for(j=0;j<vecini[x].size();j++)
     {
      nod=vecini[x][j].first;
      if(POZ[nod]) pop(POZ[nod]);
     }
    }
    g<<suma<<"\n";
    g<<n-1<<"\n";
    for(i=0;i<n-1;i++)
     g<<sol[i].first<<" "<<sol[i].second<<"\n";
    return 0;
}