#include<fstream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#define nmax 200002
using namespace std;
FILE *fin = fopen("apm.in","r");
ofstream fout("apm.out");

struct Muchie {int e1, e2, cost;};
Muchie M[nmax * 2 + 1];
int i,j , n ,m ,sel[nmax + 1];
int Nr = 0;
 long long costt = 0;
int R[nmax], T[nmax];
int x,y,c;
bool cmp(Muchie x,Muchie y)
{
    if(x.cost > y.cost)
     return 0;
    return 1;
}
int find(int x)
{
    int Rad,i ,j ;
    for(Rad = x; Rad != T[Rad] ; Rad = T[Rad]);

    for(; x != T[x]; )
    {
        int y = T[x];
        T[x] = Rad;
        x = y;

    }
    return Rad;

}
void unit(int x,int y)
{
    if(R[x] > R[y])
        T[y] = x;
        else
        T[x] = y;
    if(R[x] == R[y])
        R[x]++;
}
void det_apm()
{
    int R1,R2;
    int i, j, NrMuchii = 0;
    for(i = 1; i <= n; i++)
    {
        T[i] = i;
        R[i] = 1;
    }
    for(i = 1; NrMuchii < n - 1; i++)
    {
        R1 = find(M[i].e1);
        R2 = find(M[i].e2);
        if(R1 != R2)
        {
            unit(R1, R2);
            NrMuchii++;
            sel[++Nr] = i;
            costt += M[i].cost;
        }
    }

    fout << costt <<'\n';
    fout << Nr <<'\n';
    for(i = 1; i <= Nr; ++i)
    {
        fout <<M[sel[i]].e1 <<" " <<M[sel[i]].e2 <<'\n';

    }
}
void read()
{

    fscanf(fin, "%d %d",&n,&m);
    for(int k = 1; k <= m; ++k)
    {
        fscanf(fin,"%d %d %d",&M[k].e1 ,&M[k].e2, &M[k].cost);
       // fin >> M[k].e1 >> M[k].e2 >>M[k].cost;

    }
    sort(M + 1, M + m + 1, cmp);

    det_apm();


}
int main()
{
    read();
   fclose(fin);
    return 0;
}