#include<cstdio>
#include<algorithm>
#include<fstream>

using namespace std;

const int NMAX = 20000;
const int MMAX = 40000;

struct graf
{
    int x,y,c;

    void initializare(int _x,int _y,int _c)
    {
        x = _x;
        y = _y;
        c = _c;
    }

    bool operator()(const graf &A,const graf &B)
    {
        return A.c < B.c;
    }
};

void citire(),Krushkal(),afisare();

int N,M,cost_grag;
graf E[MMAX];
int Muchii[NMAX];

int Tata[NMAX];
int Inaltime[NMAX];

int Caut_tata(int x)
{
    if(Tata[x] != x) Tata[x] = Caut_tata(Tata[x]);
    return Tata[x];
}

void adaug(int x,int y)
{
    if(Inaltime[x] < Inaltime[y])
    {
        Tata[x] = y;
        return;
    }
    if(Inaltime[x] > Inaltime[y])
    {
        Tata[y] = x;
        return;
    }
    Tata[x] = y;
    Inaltime[y]++;
}

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

    return 0;
}

void citire()
{
    int i,x,y,c;

    ifstream f("apm.in");
    f>>N>>M;

    for(i = 1; i <= M; i++)
    {
        f>>x>>y>>c;
        E[i].initializare(x,y,c);
    }
}

void Krushkal()
{
    int i,j,x,y,c;

    sort(E+1,E+M+1,graf());

    for(i = 1; i <= N; i++)
        Tata[i] = i;

    for(i = 1, j =0 ; i <= M && j <= N-1; i++)
    {
        x = E[i].x;
        y = E[i].y;
        c = E[i].c;

        if(Caut_tata(x) == Caut_tata(y)) continue;

        adaug(Caut_tata(x),Caut_tata(y));
        cost_grag += c;
        Muchii[++j] = i;
    }
}

void afisare()
{
    int i;
    ofstream f("apm.out");
    f<<cost_grag<<" "<<N-1;

    for(i = 1; i <= N-1; i++)
        f<<E[Muchii[i]].y<<" "<<E[Muchii[i]].x<<endl;
}