#include <fstream>
#include <vector>
using namespace std;

#define nmax 200010
#define inf 200000200

vector < pair<int,int> > graf[nmax], VRASP;
int poz[nmax], vec[nmax], cost_min[nmax];
int heap[nmax];
int N = 0;

void urca(int loc)
{
    int x;
    int aux;
    while((x=loc/2) && cost_min[heap[loc]]<cost_min[heap[x]])
    {
         swap( heap[x], heap[loc] );
         swap( poz[heap[x]], poz[heap[loc]] );
         loc = x;
    }
}

void coboara(int loc)
{
    int aux, x, y = 0;
    while (loc != y)
    {
	     y = loc;
	     if ((x=y*2)<=N && cost_min[heap[loc]]>cost_min[heap[x]]) loc = x;
         x++;
	     if (x<=N && cost_min[heap[loc]]>cost_min[heap[x]]) loc = x;
         swap( heap[loc], heap[y] );
         swap( poz[heap[loc]], poz[heap[y]] );
	}
}

void add(int x)
{
    int nod;
    int cost;
    vector< pair<int,int> >::iterator it;
    for(it=graf[x].begin(); it<graf[x].end(); it++)
    {
         nod = (*it).first;
         cost = (*it).second;
         if(cost<cost_min[nod])
         {
              cost_min[nod] = cost;
              vec[nod] = x;
          }
     }
}


int main()
{
    int n, m;
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    int x, y, c;
    int i;
    for(i=0;i<m;i++)
    {
         f>>x>>y>>c;
         graf[x].push_back(make_pair(y,c));
         graf[y].push_back(make_pair(x,c));
    }

    for(i=1;i<=n;i++)
    {
         cost_min[i]=inf;
    }
    cost_min[1]=0;
    poz[1]=0;
    add(1);
    for(i=2;i<=n;i++)
    {
         heap[++N]=i;
         poz[i]=N;
         urca(N);
    }
    
    int nod;
    vector<pair<int,int> >::iterator it;
    long long suma=0; 
    
    for(i=1; i<n; i++)
    {
         x = heap[1];
         heap[1] = heap[N];
         poz[heap[1]] = 1;
         N--;        
         coboara(1);
         poz[x] = 0;
         add(x);
         VRASP.push_back(make_pair(x,vec[x]));
         suma += cost_min[x];
         for(it=graf[x].begin(); it<graf[x].end(); it++)
              if(poz[(*it).first]) urca(poz[(*it).first]);          
    }
   
    g<<suma<<'\n';
    n--;
    g<<n<<'\n';
    for(i=0;i<n;i++) g<<VRASP[i].first<<" "<<VRASP[i].second<<'\n';
   
    return 0;
}