#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <queue>
#include <map>

using namespace std;

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

struct edge
{
    int x, y, cost;

    edge(int _x = 0, int _y = 0, int _cost = 0)
        : x(_x), y(_y), cost(_cost) {}

    friend bool operator>(const edge& e1, const edge& e2)
    {
        return e1.cost > e2.cost;
    }
};

struct adj
{
    int to, cost;

    adj(int _to = 0, int _cost = 0)
        : to(_to), cost(_cost) {}

    friend bool operator<(const adj& a1, const adj& a2)
    {
        return a1.cost < a2.cost;
    }
};

vector<edge> prim(map<int, vector<adj>>& adjs, int n, int m)
{
    vector<edge> result;
    vector<bool> selected(n + 1, false);
    priority_queue<edge, vector<edge>, greater<edge>> pq;

    // Nu e important nodul de start
    selected[1] = true;
    for(const auto& a : adjs[1])
        pq.push(edge(1, a.to, a.cost));

    while(result.size() != n - 1)
    {
        edge e;

        do {
            e = pq.top();
            pq.pop();
        } while(selected[e.x] == selected[e.y]);

        result.push_back(e);

        if(!selected[e.x])
        {
            selected[e.x] = true;
            for(const auto& a : adjs[e.x])
                pq.push(edge(e.x, a.to, a.cost));
        }
        else
        {
            selected[e.y] = true;
            for(const auto& a : adjs[e.y])
                pq.push(edge(e.y, a.to, a.cost));
        }
    }

    return result;
}

int main()
{
    int n, m;

    fin >> n >> m;

    map<int, vector<adj>> adjs;

    for(int i = 1; i <= n; i++)
        adjs[i] = {};

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

        adjs[x].push_back(adj(y, cost));
        adjs[y].push_back(adj(x, cost));
    }

    vector<edge> result = prim(adjs, n, m);

    auto add_edge = [](int acc, edge e)
    {
        return acc + e.cost;
    };

    fout << accumulate(result.begin(), result.end(), 0, add_edge) << '\n' << n - 1 << '\n';

    for(const auto& e : result)
        fout << e.x << ' ' << e.y << '\n';

    fin.close();
    fout.close();

    return 0;
}