#include <bits/stdc++.h>

using namespace std;

const int N = 200005;
const int M = 400005;

struct alfa
{
    int a, b;
    int cost;
};

alfa make_triple(int a, int b, int c)
{
    alfa rez;
    rez.a = a; rez.b = b; rez.cost = c;
    return rez;
}

bool cmp(alfa a, alfa b)
{
    return a.cost < b.cost;
}

alfa muchii[M];
int n, m, suma;
int multimi[N];
vector < pair <int, int> > rez;

inline int root(int x)
{
    int rez = x;
    for (; rez != multimi[rez]; rez = multimi[rez]);
    for (; x != multimi[x]; x = multimi[rez])
        multimi[x] = rez;
    return rez;
}

inline void unite(int a, int b)
{
    a = root(a);
    b = root(b);
    multimi[b] = a;
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 1, a, b, c; i <= m; i++)
        scanf("%d %d %d", &a, &b, &c),
        muchii[i] = make_triple(a, b, c);
    sort(muchii + 1, muchii + m + 1, cmp);
    for (int i = 1; i <= n; i++)
        multimi[i] = i;
    for (int i = 1; i <= m && rez.size() < n - 1; i++)
        if (root(muchii[i].a) != root(muchii[i].b))
        unite(muchii[i].a, muchii[i].b),
        suma += muchii[i].cost,
        rez.push_back(make_pair(muchii[i].a, muchii[i].b));
    printf("%d\n%d\n", suma, rez.size());
    for (const auto &it : rez)
        printf("%d %d\n", it.first, it.second);
    return 0;
}