#include <fstream>
#include <queue>
#define NMAX 200001
#define MMAX 400001

using namespace std;
ifstream fin("");
ofstream fout("");
struct muchie
{
    int x,y,c;
    friend bool operator>(muchie a, muchie b);

};
priority_queue<muchie, vector <muchie>, greater <muchie> > H;
vector<muchie> A;
int cmin;
int n,m;
int tata[NMAX];
int h[NMAX]; ///

int Find (int x) /// O(n)
{
    int rad=x,y;
    while(tata[rad])
        rad=tata[rad];
    ///facem compresia drumului
    if(rad!=x)
    {
        y=tata[x];
        while(y!=rad)
        {
            tata[x]=rad;
            x=y;
            y=tata[x];
        }
    }
    return rad;
}
void Union (int x, int y)
{
    int i,j;
    i=Find(x), j=Find(y);
    if(i!=j) tata[j]=i;
    if(i!=j)
        if(h[i]<h[j])
            tata[i]=j;
        else if(h[i]>h[j])
            tata[j]=i;
        else
            tata[i]=j, h[j]++;
}
void citire();
void kruskal();
void afisare();

int main()
{
    citire();
    kruskal();
    afisare();

    return 0;
}
void citire()
{
    int i;
    muchie=aux;
    fin >> m >> n;
    for(i=0; i<=m; i++)
    {
        fin >> aux.x >> aux.y >> aux.c;
        H.push(aux);

    }

}
void kruskal()
{
    int i,j;
    muchie=aux;
    while(A.size()<n-1)
    {
        aux=H.top();
        H.pop();
        i=Find(aux.x),j=Find(aux.y);
        if(i!=j)
        {
            A.push_back(aux);
            cmin+=aux.c;
            Union(i,j);
        }
    }
}
void afisare()
{
    int i;
    fout << cmin << '\n';
    fout << n-1 << '\n';
    for(i=0; i<n-1; i++)
        fout <<A[i].x << ' ' << A[i].y << '\n';
}