#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int  i,j,m,n,componente[200000],conexe,suma,muc;
struct muchii
{
   int x,y;
   int c;
   bool viz;
}s1;
vector <muchii> T;
vector <muchii>::iterator it;
bool comparare(muchii aux1,muchii aux2)
{
    return aux1.c<aux2.c;
}
void UnionFind()
{
    for(i=1;i<n+1;i++)
        if(componente[i]==componente[it->y]) componente[i]=componente[it->x];
it->viz=true;
suma=suma+it->c;
muc++;
conexe--;
}
void kruskal()
{
    conexe=n;
    for(it=T.begin();it<T.end();it++)
      {
        if(conexe==1) break;
        if(componente[it->x]!=componente[it->y]) UnionFind();
      }
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin>>n>>m;
    for(i=1;i<m+1;i++)
    {
        fin>>s1.x;
        fin>>s1.y;
        fin>>s1.c;
        T.push_back(s1);
    }
    sort(T.begin(),T.end(),comparare);
    for(i=1;i<n+1;i++)
        componente[i]=i;
    kruskal();
    fout<<suma<<"\n";
    fout<<muc<<"\n";
    for(it=T.begin();it<T.end();it++)
        if(it->viz==true) fout<<it->x<<" "<<it->y<<"\n";
    fin.close();
    fout.close();
    return 0;




}