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

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

struct A
{
    int nod, cost;
};

struct B
{
    B(int _nod1, int _nod2, int _cost) : nod1 { _nod1 }, nod2  { _nod2 }, cost { _cost }
    {}

    int nod1, nod2, cost;

    bool operator< (const B& other) const { return cost < other.cost; }
    bool operator> (const B& other) const { return cost > other.cost; }
};

int n, m;
vector<A> G[200001];
vector<B> muchi;

void Citire();
void Rezolvare();

int main()
{
    Citire();
    Rezolvare();

    int sum = 0;
    for (const B& i : muchi)
    {
        sum += i.cost;
    }

    fout << sum << '\n';
    fout << muchi.size() << '\n';

    for (const B& i : muchi)
    {
        fout << i.nod1 << ' ' << i.nod2 << '\n';
    }

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

void Citire()
{
    fin >> n >> m;

    int x, y, c;
    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y >> c;
        G[x].push_back({ y, c });
        G[y].push_back({ x, c });
    }
}

void Rezolvare()
{
    bitset<200001> vizitat;
    priority_queue<B, vector<B>, greater<B>> Q;
    for (const A& i : G[1]) { Q.push({ 1, i.nod, i.cost }); }
    vizitat[1] = true;

    while (!Q.empty())
    {
        B muchie = Q.top();
        Q.pop();
        if (!vizitat[muchie.nod2])
        {
            vizitat[muchie.nod2] = true;

            for (const A& vecin : G[muchie.nod2])
            {
                if (!vizitat[vecin.nod]) { Q.push({ muchie.nod2, vecin.nod, vecin.cost }); }
            }

            muchi.push_back(muchie);
        }
    }
}