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

using namespace std;

vector<int> p;
vector<pair<int, pair<int, int> > > muc;
vector<pair<int, int> > sol;

inline int getSet(int x)
{
    return (x == p[x]) ? x : (p[x] = getSet(p[x]));
}

inline void unite(int a, int b)
{
    sol.push_back(make_pair(a, b));
    a = getSet(a);
    b = getSet(b);

    if (a % 2 == b % 2)
        p[a] = b;
    else
        p[b] = a;
}

inline void unite(const pair<int, int> &p)
{
    return unite(p.first, p.second);
}

int main()
{
    freopen("apm.in", "rt", stdin);
#ifndef DEBUG
    freopen("apm.out", "wt", stdout);
#endif

    int N, M;
    scanf("%d %d", &N, &M);
    p.reserve(N);
    for (int i = 0; i < N; i++)
        p.push_back(i);

    for (; M; M--)
    {
        int a, b, cst;
        scanf("%d %d %d", &a, &b, &cst);
        a--; b--;

        muc.push_back(make_pair(cst, make_pair(a, b)));
    }

    sort(muc.begin(), muc.end());
    int CST = 0;
    for (size_t k = 0; k < muc.size(); k++)
    {
        if (getSet(muc[k].second.first) == getSet(muc[k].second.second))
            continue;

        CST += muc[k].first;
        unite(muc[k].second);
    }

    printf("%d\n%d\n", CST, N - 1);
    for (int k = 0; k < N - 1; k++)
        printf("%d %d\n", sol[k].first + 1, sol[k].second + 1);

    return 0;
}