#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector < pair <int, int > > M[200001];
int n,m,c,Viz[200001],tata[200001],costtot,s[200001],d[200001],nr;
void Citire()
{ int i,x,y,c;
f>>n>>m;
for(i=1;i<=m;i++)
    {f>>x>>y>>c;
     M[x].push_back(make_pair(y,c));
     M[y].push_back(make_pair(x,c));
}
}
void Prim()
{ int i,j,k,minn,S,D;
    for(i=1;i<=n;i++)
   {
     Viz[i]=0;
     tata[i]=0;
   }
   costtot=0;
   Viz[1]=1;
   for(k=1;k<=n-1;k++)
   {minn=INT_MAX-10;
       for(i=1;i<=n;i++)
         for(j=0;j<M[i].size();j++)
            if(Viz[i]==1&&Viz[M[i][j].first]==0&&minn>M[i][j].second)
             {minn=M[i][j].second;
             S=i; D=M[i][j].first;
             }
       Viz[D]=1;
       tata[D]=S;
     s[nr]=S;
     d[nr]=D;
     nr++;
       costtot=costtot+minn;
   }
   g<<costtot<<endl;
 g<<nr<<endl;
}
void Afis()
{ int i;
    for(i=0;i<nr;i++)
        g<<s[i]<<" "<<d[i]<<endl;

}
int main()
{
Citire();
Prim();
Afis();
f.close();
g.close();
    return 0;
}