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

/**
 Algoritmul lui Prim - Jarnick
*/

using namespace std;

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

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;
    }
};

priority_queue<muchie> Q;
vector<muchie> G[NMAX];

int N, M, COST = 0;
int T[NMAX], D[NMAX];

bool viz[NMAX]; ///viz[i] = 1 <=> nodul i a fost selectat

void citire()
{
    ifstream f("apm.in");
    f >> N >> M;
    int x, y, cost;
    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()
{
    int nealese = N;
    while(nealese)
    {
        int x = 0; ///(*)
        while(viz[x])
        {
            x = Q.top().y;
            Q.pop();
        }
        viz[x] = true;
        COST += D[x];
        nealese--;
        for(auto &m : G[x])
            if(m.w < D[m.y] && viz[m.y] == false)
            {
                T[m.y] = x;
                D[m.y] = m.w;
                Q.push(muchie(m.y, m.w));
            }
    }
}

void afisare()
{
    ofstream g("apm.out");
    g << COST << '\n' << N - 1 << '\n';
    for(int i = 2; i <= N; ++i)
        g << i << ' ' << T[i] << '\n';
    g.close();
}

int main()
{
    citire();
    for(int i = 2; i <= N; ++i)
        D[i] = INF;
    Q.push(muchie(1, 0));
    viz[0] = true; ///artificiu (*)
    Prim();
    afisare();
    return 0;
}