#include <bits/stdc++.h>

using namespace std;

const int MMAX=(4*(1e5));

int N, M, i, j;

struct muchie
{
    int X, Y, C;
};

muchie A[MMAX+5];

int cnt;

int poz[MMAX+5], T[MMAX+5];

long long ans;

bool cmp (muchie AA, muchie BB)
{
    if(AA.C > BB.C)
        return false;
    else if(AA.C == BB.C && AA.X > BB.X)
        return false;
    else if(AA.C == BB.C && AA.X == BB.X && AA.Y > BB.Y)
        return false;
    else return true;
}

int multime (int X)
{
    if(T[X]!=X)
        T[X]=multime(T[X]);

    return T[X];
}

bool ok (int A, int B)
{
    A=multime(A);
    B=multime(B);

    if(A==B)
        return false;
    else return true;
}

void marcare (int A, int B)
{
    A=multime(A);
    B=multime(B);

    T[A]=B;
}

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

    scanf("%d%d", &N, &M);

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

    for(i=1; i<=M; i++)
        scanf("%d%d%d", &A[i].X, &A[i].Y, &A[i].C);

    sort(A+1, A+M+1, cmp);

    for(i=1; i<=M; i++)
    {
        if(ok(A[i].X, A[i].Y))
        {
            marcare(A[i].X, A[i].Y);

            ans+=A[i].C;

            poz[++cnt]=i;
        }
    }

    printf("%d\n", ans);
    printf("%d\n", cnt);

    for(i=1; i<=cnt; i++)
    {
        printf("%d ", A[poz[i]].Y);
        printf("%d\n", A[poz[i]].X);
    }

    return 0;
}