#include<fstream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#define nmax 200009
using namespace std;
FILE *fin = fopen("apm.in","r");
ofstream fout("apm.out");
int IND[nmax * 2+ 1];
int e1[nmax * 2], e2[nmax *2], cost[nmax *2];

int i,j , n ,m ,sel[nmax ];
int Nr = 0;
long long costt = 0;
int R[nmax], T[nmax];
int x,y,c;
bool cmp(int x,int y)
{
    return (cost[x]< cost[y]);
}
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)
{

        T[x] = y;

}
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(e1[IND[i]]);
        R2 = find(e2[IND[i]]);
        if(R1 != R2)
        {
            unit(R1, R2);
            NrMuchii++;
            sel[++Nr] = IND[i];
            costt += cost[IND[i]];
        }
    }

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

    }
}
void read()
{

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

    }
    for(int k = 1; k <= m;k++)
        IND[k] = k;
    sort(IND + 1, IND + m + 1, cmp);

    det_apm();


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