#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <limits.h>
#include <stdio.h>
#include <string.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector < pair <int, int> > L[200001];
int Tata[200001], Viz[200001],S[200001];
priority_queue <pair <int, int> > Q;
int n, m,costot;
inline void Citire()
{ int i, x,y,c;
    f>>n>>m;
    for(i=1;i<=m;i++)
    { f>>x>>y>>c;
        L[x].push_back(make_pair(y,c));
        L[y].push_back(make_pair(x,c));
    }
}
inline void Prim(int Start)
{int k,j,c,i,val,nod;
for(i=1;i<=n;i++)
    S[i]=INT_MAX;
S[Start]=0;
Q.push(make_pair(0, Start));
 while(!Q.empty())
 { j=Q.top().second;
   Viz[j]=1;
   Q.pop();
  for(i=0;i<L[j].size();i++)
   { val=L[j][i].second; nod=L[j][i].first;
     if(val<S[nod]&&Viz[nod]==0)
    { S[L[j][i].first]=val;
       Q.push(make_pair(-val,nod));
       Tata[nod]=j;
    }
   }
 }
}
int main()
{ int i;
Citire();
Prim(1);
for(i=1;i<=n;i++)
 costot=costot+S[i];
g<<costot<<'\n';
g<<n-1<<'\n';
 for(i=2;i<=n;i++)
    g<<Tata[i]<<" "<<i<<endl;
f.close();
g.close();
    return 0;
}