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

const int NMAX = 200010;

int N, M, X, Y, C, Cost, Father[NMAX], Size[NMAX];
vector<pair<int, int> > V;
pair<int, pair<int, int> > P[2 * NMAX];

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

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

void Kruskal()
{
    for(int i = 1; i <= M; ++ i)
    {
        int X = P[i].second.first, Y = P[i].second.second, C = P[i].first;
        int RootX = Find(X), RootY = Find(Y);
        if(RootX != RootY)
        {
            Cost += C;
            Merge(RootX, RootY);
            V.push_back(make_pair(X, Y));
        }
    }

    printf("%i\n%i\n", Cost, V.size());
    for(int i = 0; i < V.size(); ++ i)
        printf("%i %i\n", V[i].first, V[i].second);
}

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

    scanf("%i %i", &N, &M);
    for(int i = 1; i <= M; ++ i)
    {
        scanf("%i %i %i", &X, &Y, &C);
        P[i] = make_pair(C, make_pair(X, Y));
    }

    sort(P + 1, P + M + 1);
    for(int i = 1; i <= N; ++ i)
        Father[i] = i, Size[i] = 1;

    Kruskal();
}