#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int N, M, i, j;

struct muchie{int x, y, c, ok;};

muchie V[400005];

int APM[200004];

bool cmp(muchie A, muchie B)
{
    return A.c < B.c;
}

int main()
{

    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    cin>>N>>M;

    for(i=1;i<=M;++i)
    {
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);
        V[i].x = B;
        V[i].y = A;
        V[i].c = C;
        V[i].ok = 0;
    }

    sort(&V[1], &V[M]+1, cmp);

    //for(i=1;i<=M;++i)
      //  cout<<V[i].x<<" "<<V[i].y<<" = "<<V[i].c<<endl;

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

    int k=0, i=1, cost = 0;

    while(k < N-1)
    {

        if(APM[V[i].x] != APM[V[i].y])
        {

            cost += V[i].c;

            V[i].ok = 1;

            int x = APM[V[i].y];
            int y = APM[V[i].x];

            for(j=1;j<=N;++j)
                if(APM[j] == x)
                    APM[j] = y;
            ++k;
        }
        ++i;

    }

    cout<<cost<<"\n"<<N-1<<"\n";

    for(i=1;i<=N;++i)
        if(V[i].ok)
            cout<<V[i].x<<" "<<V[i].y<<"\n";

    return 0;
}