#include <fstream>
#include <vector>
#define inf 2000000005
#define nmax 200005
#define mmax 400005
using namespace std;
fstream f1("apm.in", ios::in);
fstream f2("apm.out", ios::out);
int n, m, dist[nmax], nrmuc, viz[nmax], pred[nmax], co[nmax], cost;
vector <pair<int, int> > v[nmax];
struct muchii
{
    int x, y;
}muc[mmax];
void citire()
{
    int i, x, y, c;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y>>c;
        v[x].push_back({y, c});
        v[y].push_back({x, c});
    }
}
void solutie()
{
   ///dist[i]=dist min de la un varf al apm-ului la nodul i
   int i, j, vfmin, mini;
   dist[1]=0;
   for(i=2; i<=n; i++) dist[i]=inf;
   for(i=1; i<=n; i++)
   {
       vfmin=0;
       mini=inf;
       for(j=1; j<=n; j++)
           if((!viz[j])&&(mini> dist[j])) {mini=dist[j]; vfmin=j;}
       viz[vfmin]=1;
       if(vfmin!=1)
       {
           nrmuc++;muc[nrmuc].x=pred[vfmin]; muc[nrmuc].y=vfmin;
           cost+=co[vfmin];
       }
       for(auto it=v[vfmin].begin(); it!=v[vfmin].end(); ++it)
       {
           int vec=(*it).first;
           int ct=(*it).second;
           if((!viz[vec])&&(dist[vec]> ct))
           {
               dist[vec]=ct;
               pred[vec]=vfmin;
               co[vec]=ct;
           }
       }
   }
}
void afis()
{
    int i;
    f2<<cost<<"\n"<<nrmuc<<"\n";
    for(i=1; i<=nrmuc; i++)
        f2<<muc[i].x<<' '<<muc[i].y<<"\n";
}
int main()
{
    citire();
    solutie();
    afis();
    return 0;
}