#include <fstream>
#include <tuple>
#include <algorithm>

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

int n, m, t[200005], k;
tuple <int, int, int> L[400005]; /// 0 si 1 : nodurile legate, 2 : costul muchiei
pair <int, int> sol[400005];


bool Compare (tuple <int, int, int> a, tuple<int, int, int> b)
{
    return get<2> (a) < get<2> (b) ;
}

inline void Union (int x, int y)
{
    t[y] = x;
}

int Find (int x)
{
    int root, y;
    root = x;
    while (t[root] != 0)
        root = t[root];
    while (x != root)
    {
        y = t[x];
        t[x] = root;
        x = y;
    }
    return root;
}

void Read ()
{
    int i;
    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        int x, y, z;
        fin >> x >> y >> z;
        L[i] = make_tuple(x, y, z);
    }
    sort (L + 1, L + m + 1, Compare);
}

void APM ()
{
    int i, x, y, ans = 0;
    for (i = 1; i <= m; i++)
    {
        x = get <0> (L[i]);
        y = get <1> (L[i]);
        x = Find (x);
        y = Find (y);
        if (x != y)
        {
            Union (x, y);
            sol[++k] = {get<0> (L[i]), get<1> (L[i])};
            ans += get<2> (L[i]);
        }
    }
    fout << ans << "\n" << k << "\n";
    for (i = 1; i <= k; i++)
        fout << sol[i].first << " " << sol[i].second << "\n";
}

int main()
{
    Read();
    APM();
    return 0;
}