#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int TT[200004],RG[200004],N,M,i,j,k,sol,poz[200004];
struct triplet{
int x;
int y;
int cost;
} v[400004];
int comp(triplet a,triplet b)
{
    if(a.cost<b.cost) return 1;
    return 0;
}
int radacina(int x)
{
    int r,y;
    r=x;
    while(TT[r]!=r)
        r=TT[r];
    while(TT[x]!=x)
    {
        y = TT[x];
		TT[x] = r;
		x = y;
    }
    return r;
}
void unite(int x, int y)
{
    if(RG[x]>RG[y])
        TT[y] = x;
        else TT[x] = y;
    if(RG[x] == RG[y]) RG[y]++;
}
int main()
{
    f>>N>>M;
    for(i=1;i<=N;i++)
    {
        TT[i]=i;
        RG[i]=1;
    }
    for(i=1;i<=M;i++)
    {
      f>>v[i].x>>v[i].y>>v[i].cost;
    }
    sort(v+1,v+M+1,comp);
    unite(radacina(v[1].x),radacina(v[1].y));
    unite(radacina(v[2].x),radacina(v[2].y));
    k=2;
    poz[1]=1;
    poz[2]=2;
    sol=v[1].cost+v[2].cost;
    for(i=3;k<N-1;i++)
    {
        if(radacina(v[i].x)!=radacina(v[i].y))
        {
            unite(radacina(v[i].x),radacina(v[i].y));
            sol=sol+v[i].cost;
            k++;
            poz[k]=i;
        }
    }
    g<<sol<<'\n';
    g<<k<<'\n';
    for(i=1;i<=k;i++)
        g<<v[poz[i]].x<<" "<<v[poz[i]].y<<'\n';
    return 0;
}