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

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

const int NMAX = 200001;
const int INF = 1 << 30;
struct nod
{
    int x, cost;
};

struct raspuns
{
    int start, stop, cost;
};

struct compara
{
    bool operator () (nod a, nod b) {
        return a.cost > b.cost;
    }
};

int Suma_Totala = 0;
int N, M;
int dist[NMAX];
int tata[NMAX];
int viz[NMAX];
std::priority_queue <nod,std::vector<nod>, compara > Q;
std::vector<std::pair<int, int>>G[NMAX];
std::vector<raspuns> Rez;

void Citire()
{
    fin >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        G[x].push_back({ y,cost });
        G[y].push_back({ x,cost });
    }
}

void Initializare()
{
    for (int i = 1; i <= N; ++i)
    {
        dist[i] = INF;
        tata[i] = 0;
       
    }
    dist[1] = 0;
    for (int i = 1; i <= N; ++i)
    {
        nod a;
        a.x = i;
        a.cost = dist[i];
        Q.push(a);
    }

}

void test_coada()
{
    while (!Q.empty())
    {
        std::cout << Q.top().x << " " << Q.top().cost << '\n';
        Q.pop();
    }
}

void Prim()
{
    int nr_varfuri = N-1;
    while (nr_varfuri)
    {
        while (viz[Q.top().x] == 1)
            Q.pop();
        nod nod_ieftin = Q.top();
        Q.pop();
        viz[nod_ieftin.x] = 1;
        if (tata[nod_ieftin.x] != 0)
        {
            raspuns r;
            r.start = tata[nod_ieftin.x];
            r.stop = nod_ieftin.x;
            r.cost = nod_ieftin.cost;
            Rez.push_back(r);
            nr_varfuri--;
            Suma_Totala += nod_ieftin.cost;
        }
        nod nod_minim;
        nod_minim.x = 0;
        nod_minim.cost = INF;
        for (auto vecin : G[nod_ieftin.x])
        {
            if (viz[vecin.first] == 0) 
            {
                if (dist[vecin.first] > vecin.second)
                {
                    dist[vecin.first] = vecin.second;
                    tata[vecin.first] = nod_ieftin.x;
                    nod nou;
                    nou.x = vecin.first;
                    nou.cost = vecin.second;
                    Q.push(nou);

                }
                if (dist[vecin.first] < nod_minim.cost)
                {
                    nod_minim.cost = dist[vecin.first];
                    nod_minim.x = vecin.first;
                }
            }
        }
    }
}

void Afisare()
{
    fout << Suma_Totala << '\n';
    fout << N - 1 << '\n';
    for (auto raspuns : Rez)
    {
        fout << raspuns.start << " " << raspuns.stop << '\n';
    }
}


int main()
{
    Citire();
    Initializare();
    //test_coada();
    Prim();
    Afisare();
}