#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{int x; int y; int c;}m[400005];
vector <muchie> APM;
struct nod{int T; int R;} n[200005];
int x,y,c,N,M,t,componente,cost;
bool conditie(muchie lhs, muchie rhs) {return lhs.c<rhs.c;}
int Find(int x)
{
    if(n[x].T!=x) n[x].T=Find(n[x].T);
    return n[x].T;
}
int Union(int x, int y)
{
    int xRoot,yRoot;
    xRoot=Find(x);
    yRoot=Find(y);
    if(xRoot==yRoot) return 0;
    if(n[xRoot].R<n[yRoot].R)
    {
        n[xRoot].T=yRoot;
        n[yRoot].R+=n[xRoot].R;
    }
    else
    {
        n[yRoot].T=xRoot;
        n[xRoot].R+=n[yRoot].R;
    }
    componente--;
    return 0;
}
void Make_Set(int M)
{
    componente=N;
    for(int i=1;i<=M;i++)
    {
        n[i].T=i;
        n[i].R=1;
    }
}
int main()
{
    fin>>N>>M;
    Make_Set(M);
    for(int i=1;i<=N;i++)
    {
        fin>>m[i].x>>m[i].y>>m[i].c;
    }
    sort(m+1,m+M+1,conditie);
    for(int i=1;i<=M;i++)
    {
        if(componente==1) break;
        x=m[i].x;
        y=m[i].y;
        c=m[i].c;
        if(Find(x)!=Find(y))
        {
            cost+=c;
            Union(x,y);
            muchie temp={x,y,c};
            APM.push_back(temp);
        }
    }
    fout<<cost<<'\n';
    fout<<N-1<<'\n';
    for(int i=0;i<N-1;i++)
    {
        fout<<APM[i].y<<' '<<APM[i].x<<'\n';
    }
    return 0;
}