#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int t[200005], h[200005];

struct s
{
    int u, v, c;
};

struct s1
{
    int u, v;
};

bool cmp(s a, s b)
{
    return a.c < b.c;
}

vector<s> v;
vector<s1> sol;

int finds(int u)
{
    while(t[u] != u)
    {
        u = t[u];
    }
    return u;
}

void unions(int u, int v)
{
    if(h[u] == h[v]) { t[u] = v; h[u]++; }
    else if(h[u] > h[v]) { t[v] = u; }
    else { t[u] = v; }
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int n, m, c = 0, cnt = 0, i = 0;
    s tmp;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &tmp.u, &tmp.v, &tmp.c);
        v.push_back(tmp);
    }
    sort(v.begin(), v.end(), cmp);
    for(int i = 0; i < n; i++) t[i] = i;
    for(int i = 0; i < n; i++) h[i] = 0;
    while(cnt < n - 1)
    {
        if(finds(v[i].u) != finds(v[i].v))
        {
            unions(v[i].u, v[i].v);
            c += v[i].c;
            cnt++;
            sol.push_back({v[i].u, v[i].v});
        }
        i++;
    }
    printf("%d\n%d\n", c, n - 1);
    for(int i = 0; i < sol.size(); i++)
    {
        printf("%d %d\n", sol[i].v, sol[i].u);
    }
    return 0;
}