#include <fstream>
#include <algorithm>
#define in "apm.in"
#define out "apm.out"
#define Max_Size 200009

std :: ifstream f(in);
std :: ofstream g(out);

int N, M, Sum, Dim;
int T[Max_Size], R[Max_Size];
struct nod
{
    int _fnod;
    int _snod;
    int _cost;
};
 nod A[Max_Size * 2], Arb[Max_Size * 2];

inline void Read_Data()
{
    f >> N >> M;

    for(int i = 1; i <= M; ++i)
        f >> A[i]._fnod >> A[i]._snod >> A[i]._cost;
}

inline bool  cmp(nod a, nod b)
{
    return (a._cost < b._cost);
}

inline int Find(int x)
{
    int Root;
    for(Root = x; Root != T[Root]; Root = T[Root]);

    int y;
    while(x != T[x])
    {
        y = T[x];
        T[x] = Root;
        x = y;
    }

    return Root;
}

inline void Union(int x, int y)
{
    if(R[x] < R[y]) T[x] = y;
    else            T[y] = x;

    if(R[x] == R[y]) ++R[y];
}

void Solve()
{
    int x, y;

    std :: sort(A + 1, A + M + 1, cmp);
    for(int i = 1; i <= N; ++i) T[i] = i, R[i] = 1;

    for(int i = 1; i <= M; ++i)
    {
        x = Find(A[i]._fnod);
        y = Find(A[i]._snod);

        if(x != y)
        {
            Union(x, y);
            Arb[++Dim] = A[i];
        }
    }

    for(int i = 1; i <= Dim; ++i)   Sum += Arb[i]._cost;
}

inline void Write_Data()
{
    g << Sum << '\n' << Dim << '\n';
    for(int i = 1; i <= Dim; ++i)
        g << Arb[i]._fnod << ' ' << Arb[i]._snod << '\n';
}

int main()
{
    Read_Data();
    Solve();
    Write_Data();

    g.close();
    return 0;
}