#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <queue>
#include <tuple>

const int Inf = 0x3f3f3f3f;
const int MaxN = 200001;

struct Edge{
    Edge() : node{0}, key{0}
    {}

    Edge(int node, int key) : node{node}, key{key}
    {}

    bool operator < (const Edge& e) const
    {
        return key  > e.key;
    }

    int node, key;
};

using VI = std::vector<int>;
using VP = std::vector<std::pair<int, int>>;
using VVP = std::vector<VP>;

void ReadData();
void Prim(int x);
void Write();

int n;
std::bitset<MaxN> v;
VI key;
VVP G;
VP apm;
long long cost_apm;

int main()
{
    ReadData();
    Prim(1);
    Write();
}

void ReadData()
{
    std::ifstream fin("apm.in");

    int a, b, w, m;
    fin >> n >> m;
    G = VVP(n + 1);

    while (m--)
    {
        fin >> a >> b >> w;

        G[a].emplace_back(b, w);
        G[b].emplace_back(a, w);
    }
}

void Prim(int x)
{
    std::priority_queue<Edge> Q;
    key = VI(n + 1, Inf);
    VI t = VI(n + 1);

    key[x] = 0;
    int y, ky;
    Q.emplace(x, 0);

    while (!Q.empty())
    {
        x = Q.top().node;
        v[x] = 1;

        for (auto& p : G[x])
        {
            std::tie(y, ky) = p;
            if (v[y])
                continue;

            if (key[y] > ky)
            {
                key[y] = ky;
                t[y] = x;
                Q.emplace(y, key[y]);
            }
        }

        apm.emplace_back(x, t[x]);
        cost_apm += key[x];
        while (!Q.empty() && v[Q.top().node])
            Q.pop();
    }
}

void Write()
{
    std::ofstream fout("apm.out");

    fout << cost_apm << '\n' << n - 1 << '\n';

    //std::sort(apm.begin(), apm.end());

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