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

#define pii pair <int, int>
#define f first
#define s second

using namespace std;

vector <int> v[200010];
vector <pii> arb;

int t[200010], vol[200010];
pair <pii, int> sir[400010];

inline bool comp (pair <pii, int> a, pair <pii, int> b)
{
    return a.s < b.s;
}

inline int fin (int a)
{
    if (t[a] == a) return a;
    return (t[a] = fin (t[a]));
}

inline void uneste (int a, int b)
{
    vol[t[b]] += vol[t[a]];
    vol[t[a]] = 0;
    t[t[a]] = t[b];
}

int main ()
{
    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);

    int n, m;
    scanf ("%d %d", &n, &m);

    for (int i = 1; i <= n; ++i)
        t[i] = i, vol[i] = 1;

    for (int i = 1; i <= m; ++i)
        scanf ("%d %d %d", &sir[i].f.f, &sir[i].f.s, &sir[i].s);

    sort (sir + 1, sir + m + 1, comp);

    int cost = 0;
    for (int i = 1; i <= m && vol[fin (1)] < n; ++i)
    {
        if (fin (sir[i].f.f) == fin (sir[i].f.s)) continue;
        cost += sir[i].s;

        uneste (sir[i].f.f, sir[i].f.s); /// deja am restrans multimea deci nu mai trebuie sa facem fim
        arb.push_back (sir[i].f);
    }

    printf ("%d\n%d\n", cost, arb.size ());

    for (auto &it : arb)
        printf ("%d %d\n", it.f, it.s);

    return 0;
}