#include <bits/stdc++.h>
#define NMAX 200008

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

struct Muchie
{
    int x, c, tata;
};

struct comparare
{
    bool operator() (const Muchie & a, const Muchie & b)
    {
        return a.c > b.c;
    }
};

int n, m, total, t[NMAX], h[NMAX];
bool viz[NMAX];
priority_queue <Muchie, vector<Muchie>, comparare> H;
vector < pair <int, int> > G[NMAX], sol;

void Prim();

int main()
{
    int x, y, z;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        G[x].push_back({y, z});
        G[y].push_back({x, z});
    }
    Prim();
    return 0;
}

void Prim()
{
    H.push({1, 0, 0});
    while (!H.empty())
    {
        int nod = H.top().x;
        int cost = H.top().c;
        int tata = H.top().tata;
        H.pop();
        if (viz[nod])
            continue;
        viz[nod] = 1;
        total += cost;
        sol.push_back({tata, nod});

        for (auto vf : G[nod])
            if (!viz[vf.first])
                H.push({vf.first, vf.second, nod});
    }
    fout << total << '\n' << sol.size()-1 << '\n';
    for (int i = 1; i < sol.size(); i++)
        fout << sol[i].first << ' ' << sol[i].second << '\n';
}