#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <set>
#include <algorithm>

#define inf 1e9

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

struct Muchie
{
    int x, y, cost;
};
struct Node
{
    int x, cost;
};
bool operator<(const Node& a, const Node& b)
{
    if (a.cost == b.cost)
        return a.x < b.x;
    return a.cost < b.cost;
}

bool CompareMuchii(const Muchie& a, const Muchie& b)
{
    if (a.cost == b.cost)
    {
        if (a.x == b.x)
            return a.y < b.y;
        return a.x < b.x;
    }
    return a.cost < b.cost;
}


vector<int> tata;
vector<int> level;

int Repr(int x)
{
    if (tata[x] == -1)
        return x;

    tata[x] = Repr(tata[x]);
    return tata[x];
}
void Reuniune(int x, int y)
{
    int repr_x = Repr(x);
    int repr_y = Repr(y);

    if (repr_x == repr_y)
        return;

    if (level[repr_x] <= level[repr_y])
    {
        tata[repr_x] = repr_y;
        if (level[repr_x] == level[repr_y])
            level[repr_y]++;
    }
    else
    {
        tata[repr_y] = repr_x;
        if (level[repr_x] == level[repr_y])
            level[repr_y]++;
    }
}

vector<Muchie> Kruskal(int n, vector<Muchie> &listaMuchii)
{
    tata.assign(n, -1);
    level.assign(n, 1);
    vector<Muchie> ans;

    sort(listaMuchii.begin(), listaMuchii.end(), CompareMuchii);
    int sel = 0;

    for (Muchie &m : listaMuchii)
    {
        cout << Repr(m.x) << Repr(m.y) << endl;
        if (Repr(m.x) == Repr(m.y)) continue;

        Reuniune(m.x, m.y);
        ans.push_back(m);
        sel++;

        if (sel == n - 1)
            break;
    }

    return ans;
}
vector<Muchie> Prim(int n, vector<vector<Node>> &listaVecini)
{
    // start node - 0
    vector<int> d(n, inf);
    vector<int> tata(n, -1);
    vector<bool> viz(n, false);

    vector<Muchie> ans;

    set<Node> Set;
    Set.emplace(0, 0);
    d[0] = 0;

    while (!Set.empty())
    {
        Node nod = *Set.begin();
        Set.erase(Set.begin());
        viz[nod.x] = true;

        for (Node &v : listaVecini[nod.x])
        {
            if (viz[v.x] == false && v.cost < d[v.x])
            {
                if (d[v.x] != inf)
                    Set.erase(Set.find(Node(v.x, d[v.x])));
                Set.emplace(v.x, v.cost);
                d[v.x] = v.cost;
                tata[v.x] = nod.x;
            }
        }

        if (nod.x != 0)
            ans.emplace_back(nod.x, tata[nod.x], d[nod.x]);
    }

    return ans;
}

int main()
{
    int n, m; in >> n >> m;
    vector<Muchie> listaMuchii(m);
    vector<vector<Node>> listaVecini(n);

    for (int i = 0; i < m; i++)
    {
        int x, y, cost; in >> x >> y >> cost;
        x--; y--;
        listaMuchii[i] = Muchie(x, y, cost);
        listaVecini[x].emplace_back(y, cost);
        listaVecini[y].emplace_back(x, cost);
    }

    vector<Muchie> apcm = Prim(n, listaVecini);

    int totalCost = 0;
    for (Muchie &m : apcm)
        totalCost += m.cost;
    out << totalCost << "\n";
    out << apcm.size() << "\n";
    for (Muchie &m : apcm)
        out << m.x + 1 << " " << m.y + 1 << "\n";

    return 0;
}