#include <fstream>
#include <queue>
#include <functional>
#define NMAX 200001
#define MMAX 400001

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie
{
    int x,y,c;
    friend bool operator >(muchie a, muchie b);
};
bool operator >(muchie a,muchie b)
{
    return a.c>b.c;
}
priority_queue< muchie, vector<muchie>, greater<muchie> > H;
vector<muchie> A; ///apm
int cmin; ///costul apm-ului
int n,tata[NMAX],m;
int h[NMAX]; ///h[i]=inaltimea arborelui cu radacina i
int Find(int x)  ///O(n)
{
    int rad=x,y;
    while(tata[rad])
        rad=tata[rad];
    ///compresia drumului
    if(rad!=x)
    {
    y=tata[x];
    while(y!=rad)
    {
        tata[x]=rad;
        x=y;
        y=tata[x];
    }
    }
    return rad;
}
void Union(int x, int y)
{
    int i,j;
    i=Find(x);
    j=Find(y);
    if(i!=j)
        if(h[i]<h[j])
            tata[i]=j;
        else
            if(h[j]<h[i])
            tata[j]=i;
            else
            {
            tata[i]=j;
            h[j]++;
            }

}
void citire();
void kruskal();
void afisare();
int main()
{
     citire();
     kruskal();
     afisare();
    return 0;
}
void citire()
{
    int i;
    muchie aux;
    fin>>n>>m;
    for(i=0;i<m;i++)
    {
        fin>>aux.x>>aux.y>>aux.c;
        H.push(aux);
    }
}
void kruskal()
{
   muchie aux;
   int i,j;
   while(A.size()<n-1)
   {
     aux=H.top();
     H.pop();
     i=Find(aux.x);
     j=Find(aux.y);
     if(i!=j)
     {
         A.push_back(aux);
         cmin+=aux.c;
         Union(i,j);
     }
   }
}
void afisare()
{
    int i;
    fout<<cmin<<'\n';
    fout<<n-1<<'\n';
    for(i=0;i<n-1;i++)
        fout<<A[i].x<<' '<<A[i].y<<'\n';
}