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

using namespace std;

const int NMAX = 200001,
          INF = 1 << 10;

struct muchie
{
    int y, w;

    muchie(int yy = 0, int ww = 0): y(yy), w(ww) {}

    bool operator<(const muchie &m) const
    {
        return w > m.w;
    }
};

int N, M, COST, D[NMAX], T[NMAX];
bool viz[NMAX];
priority_queue<muchie> Q;
vector<muchie> G[NMAX];
vector<pair<int, int>> sol;

void citire()
{
    ifstream f("apm.in");
    int x, y, cost;
    f >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        f >> x >> y >> cost;
        G[x].push_back(muchie(y, cost));
        G[y].push_back(muchie(x, cost));
    }
    f.close();
}
void Prim()
{
    for(int i = 2; i <= N; i++)
        D[i] = INF;
    Q.push(muchie(1, 0));
    while(!Q.empty())
    {
        auto crt = Q.top();
        Q.pop();
        if(viz[crt.y]) continue;
        viz[crt.y] = 1;
        COST += D[crt.y];
        if(T[crt.y])
            sol.push_back({crt.y, T[crt.y]});
        for(const auto &m : G[crt.y])
            if(m.w < D[m.y] && !viz[m.y])
            {
                T[m.y] = crt.y;
                D[m.y] = m.w;
                Q.push(m);
            }
    }
}
void afisare()
{
    ofstream g("apm.out");
    g << COST << '\n' << sol.size() << '\n';
    for(const auto &x : sol)
        g << x.first << ' ' << x.second << '\n';
    g.close();
}

int main()
{
    citire();
    Prim();
    afisare();
    return 0;
}