#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int n,m,t[200005];

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

int k;

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




int partition(muchie vec[], int low, int high) {
    int pivot = vec[high].c;
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        if (vec[j].c < pivot) {
            i++;
            std::swap(vec[i], vec[j]);
        }
    }

    std::swap(vec[i + 1], vec[high]);
    return i + 1;
}

void quickSort(muchie vec[], int low, int high) {
    if (low < high) {
        int pi = partition(vec, low, high);

        quickSort(vec, low, pi - 1);
        quickSort(vec, pi + 1, high);
    }
}

void ordonare(int m) {
    quickSort(vec, 1, m);
}

/*
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";
     }


}