#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

int TT[200010], RG[200010];
int get_root(int x)
{
    int R = x;
    while(R != TT[R]) R = TT[R];
    while(TT[x] != x)
    {
        int y = TT[x];
        TT[x] = R;
        x = y;
    }
    return R;
}
void unite(int x, int y)
{
    if(RG[x] > RG[y])
        TT[y] = x;
    else TT[x] = y;
    if(RG[x] == RG[y]) RG[x]++;
}

struct bobu
{
    int s, d, c;
} M[400010], S[400010];
bool cmp(bobu x, bobu y)
{
    return x.c < y.c || (x.c == y.c && x.s < y.s) ||
           (x.c == y.c && x.s == y.s && x.d < y.d);
}
int n, m, Sol, k;
int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++)
        in >> M[i].s >> M[i].d >> M[i].c;
    for(int i = 1; i <= n; i++)
    {
        TT[i] = i;
        RG[i] = 1;
    }
    sort(M + 1,M + m + 1, cmp);
    for(int i = 1 ; i <= m; i++)
    {
        if(get_root(M[i].s) != get_root(M[i].d))
        {
            Sol += M[i].c;
            S[++k] = M[i];
            unite(get_root(M[i].s), get_root(M[i].d));
        }
    }
    out << Sol << '\n';
    out << k << '\n';
    for(int i = 1; i <= k; i++)
        out << S[i].s << " " << S[i].d << '\n';
    return 0;
}