#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n,m,t[400005];

struct muchie{
    int x,y,c;
};

int k;

muchie manu[400005];
muchie vec[400005];

void ordonare(int m)
{
    muchie aux;
    for(int i = 1; i <= m-1; i++)
    {
        for(int j = i+1; j <= m; j++)
        {
            if(vec[i].c > vec[j].c)
            {
                aux = vec[i];
                vec[i] = vec[j];
                vec[j] = aux;
            }
        }
    }
}
int S;
int main()
{
     fin >> n >> m;
     for(int i = 1; i <= m; i++)
     {
         fin >> vec[i].x >> vec[i].y >> vec[i].c;
     }
     ordonare(m);
     for(int i = 1; i <= n; i++)
        t[i] = i;
     for(int i = 1 ; i <= m; i++)
     {
         if(t[vec[i].x] != t[vec[i].y])
         {
             S += vec[i].c;
             k++;
             manu[k].x = vec[i].x;
             manu[k].y = vec[i].y;
             int ai = t[vec[i].x],aj = t[vec[i].y];
             for(int j = 1; j <= n; j++)
             {
                 if(t[j]==aj)
                 {
                     t[j]=ai;
                 }
             }
         }
     }
     fout<<S<<"\n";
     fout<<k<<"\n";
     for(int i=1;i<=k;i++)
     {
         fout<<manu[i].x<<" "<<manu[i].y<<"\n";
     }


}