#include <fstream>
#include <bitset>
#include <vector>
#include <set>

using namespace std;

#define FILE_NAME "apm"
ifstream fin(FILE_NAME".in");
ofstream fout(FILE_NAME".out");

const int MAX_N = 200000 + 16;

int N, M;
vector < pair < int, int > > Graf[MAX_N];
set < pair < int, pair < int, int > > > S;
vector < pair < int, int > > APM;
bitset < MAX_N > Viz;

int main()
{
    fin >> N >> M;

    for (int i = 1; i <= M; ++i)
    {
        int a, b, c;
        fin >> a >> b >> c;
        Graf[a].push_back(make_pair(c, b));
        Graf[b].push_back(make_pair(c, a));
    }

    S.insert(make_pair(0, make_pair(0, 1)));
    int vizited = 0, cost = 0;
    while (vizited != N)
    {
        while (!S.empty() && Viz.test((*S.begin()).second.second))
            S.erase(S.begin());

        auto &muc = (*S.begin());
        int nod = muc.second.second;
        cost += muc.first;
        APM.push_back(make_pair(muc.second.first, muc.second.second));

        S.erase(S.begin());
        Viz.set(nod);
        ++vizited;

        for (auto next : Graf[nod])
            S.insert(make_pair(next.first, make_pair(nod, next.second)));
    }

    fout << cost << '\n';
    fout << N-1 << '\n';

    for (unsigned i = 1; i < APM.size(); ++i)
    {
        auto &edge = APM[i];
        fout << edge.first << ' ' << edge.second << '\n';
    }

    return 0;
}