#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

#define Nmax 200010
#define PI pair<int, int>
#define mp make_pair
#define f first
#define s second
#define pb push_back

vector<PI> V;
int X[Nmax], Y[Nmax], C[Nmax], Idx[Nmax];
int Father[Nmax], Size[Nmax];
int N, M, Ans;

struct CMP
{
    bool operator() (const int &A, const int &B) const
    {
        return C[A] < C[B];
    };
};

int Find_Root(int X)
{
    int Y, P;
    for(P = X; P != Father[P]; P = Father[P]);
    for(; X != Father[X]; )
    {
        Y = Father[X];
        Father[X] = P;
        X = Y;
    }
    return P;
}

void Merge(int X, int Y)
{
    if(Size[X] > Size[Y])
    {
        Father[Y] = X;
        Size[X] += Size[Y];
    }else
    {
        Father[X] = Y;
        Size[Y] += Size[X];
    }
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int i;
    scanf("%i %i", &N, &M);
    for(i = 1; i <= N; ++ i) Father[i] = i, Size[i] = 1;
    for(i = 1; i <= M; i++)
    {
        scanf("%i %i %i", &X[i], &Y[i], &C[i]);
        Idx[i] = i;
    }
    sort(Idx + 1, Idx + M + 1, CMP());
    for(i = 1; i <= M; ++ i)
    {
        int F = X[Idx[i]], S = Y[Idx[i]], Cost = C[Idx[i]];
        if(Find_Root(F) != Find_Root(S))
        {
            Ans += Cost;
            V.pb(mp(F, S));
            Merge(Find_Root(F), Find_Root(S));
        }
    }
    printf("%i\n", Ans);
    printf("%i\n", V.size());
    for(i = 0; i < V.size(); ++ i) printf("%i %i\n", V[i].f, V[i].s);
    return 0;
}