#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int zhk[100003], gr[100003];



int find_set(int a)
{
    if (zhk[a] == a)
        return a;
    return zhk[a] = find_set(zhk[a]);

}

void union_sets(int a, int b)
{
    a = find_set(a);
    b = find_set(b);
    if (a != b)
    {
        if (gr[a] < gr[b])
        {
            swap(a, b);
        }
        zhk[b] = a;
        gr[a] += gr[b];
    }
}

struct muchie
{
    int x, y, c;
};

muchie graf[400005];
int t[200005];

bool cmp (muchie a, muchie b)
{
    if (a.c < b.c)
        return 1;
    return 0;
}

vector<muchie> sol;

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> graf[i].x >> graf[i].y >> graf[i].c;
    }
    sort(graf+1, graf+m+1, cmp);
    for (int i = 1; i <= n; i++)
        zhk[i] = i, gr[i] = 1;

    int S = 0;
    for(int i = 1 ; i <= m ; i ++)
        if(find_set(graf[i].x) != find_set(graf[i].y)) // extremitatile fac parte din subrabori diferiti
        {
            S += graf[i].c;
            //reunim subarborii
            union_sets(graf[i].x, graf[i].y);
            sol.push_back(graf[i]);
        }
    cout << S << "\n";
    cout << n-1 << '\n';
    for (auto muc: sol)
    {
        cout << muc.x << " " << muc.y << "\n";
    }
    return 0;
}