#include <fstream>
#include <queue>
#include <utility>
#include <vector>
#include <bitset>
using namespace std;

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

struct A
{
    int n1, n2, c;

    bool operator> (const A& other) const
    {
        return c > other.c;
    }
};

int n, m;
vector<pair<int, int>> G[200001];
vector<pair<int, int>> apm;
priority_queue<A, vector<A>, greater<A>> Q;
bitset<200001> v;

int main()
{
    fin >> n >> m;

    for (int i = 1, x, y, c; i <= m; ++i)
    {
        fin >> x >> y >> c;

        G[x].emplace_back(y, c);
        G[y].emplace_back(x, c);
    }

    Q.push({ 0, 1, 0 });

    int cm = 0;
    while (!Q.empty())
    {
        auto t = Q.top();
        Q.pop();

        if (v[t.n2]) { continue; }

        apm.emplace_back(t.n1, t.n2);

        cm += t.c;

        v[t.n2] = true;
        for (const auto& x : G[t.n2])
        {
            if (!v[x.first])
            {
                Q.push({ t.n2, x.first, x.second });
            }
        }
    }

    fout << cm << '\n' << (apm.size() - 1) << '\n';

    for (size_t i = 1; i < apm.size(); ++i)
    {
        fout << apm[i].first << ' ' << apm[i].second << '\n';
    }

    fin.close();
    fout.close();
    return 0;
}