#include <fstream>
#include <cmath>
#include <vector>

using namespace std;

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

const int INFINIT = 1005;
const int NMAX = 200005;

vector < vector < pair < int, int > > > costuri(NMAX);
vector < int > vx;
vector < int > vy;
int tati[NMAX], N, M;
int dist[NMAX];
int poz_in_heap[NMAX];
bool vizitat[NMAX];
long long cost_minim;
int nod_start = -1;

struct Heap
{
    int H[NMAX], lg;

    Heap()
    {
        for(int i = 0; i < NMAX; i++)
            H[i] = 0;
        lg = 0;
    }

    int pop()
    {
        int head = H[1];

        H[1] = H[lg];
        poz_in_heap[H[1]] = 1;
        poz_in_heap[head] = 0;
        H[lg] = 0; lg--;

        int cp = 1; bool este_heap = false;
        while((cp < lg && !este_heap) && H[2 * cp])
        {
            if(dist[H[2 * cp]] >= dist[H[cp]] && dist[H[2 * cp + 1]] >= dist[H[cp]])
                este_heap = true;
            else
            {
                if(dist[H[2 * cp]] < dist[H[2 * cp + 1]])
                {
                    int aux = H[2 * cp];
                    H[2 * cp] = H[cp];
                    H[cp] = aux;

                    aux = poz_in_heap[H[2 * cp]];
                    poz_in_heap[H[2 * cp]] = poz_in_heap[H[cp]];
                    poz_in_heap[H[cp]] = aux;
                    cp *= 2;
                }
                else
                {
                    int aux = H[2 * cp + 1];
                    H[2 * cp + 1] = H[cp];
                    H[cp] = aux;

                    aux = poz_in_heap[H[2 * cp + 1]];
                    poz_in_heap[H[2 * cp + 1]] = poz_in_heap[H[cp]];
                    poz_in_heap[H[cp]] = aux;
                    cp *= 2; cp++;
                }
            }
        }
        return head;
    }

    void push(int numar)
    {
        H[++lg] = numar;
        poz_in_heap[numar] = lg;
        int cp = lg; bool este_heap = false;
        while(cp > 1 && !este_heap)
        {
            if(dist[H[cp]] >= dist[H[cp / 2]])
                este_heap = true;
            else
            {
                int aux = H[cp / 2];
                H[cp / 2] = H[cp];
                H[cp] = aux;

                aux = poz_in_heap[H[cp / 2]];
                poz_in_heap[H[cp / 2]] = poz_in_heap[H[cp]];
                poz_in_heap[H[cp]] = aux;
                cp /= 2;
            }
        }
    }

    void heapify(int nod)
    {
        int poz = poz_in_heap[nod];
        if(dist[H[poz]] < dist[H[poz / 2]])
        {
            int cp = poz; bool este_heap = false;
            while(cp > 1 && !este_heap)
            {
                if(dist[H[cp]] >= dist[H[cp / 2]])
                    este_heap = true;
                else
                {
                    int aux = H[cp / 2];
                    H[cp / 2] = H[cp];
                    H[cp] = aux;

                    aux = poz_in_heap[H[cp / 2]];
                    poz_in_heap[H[cp / 2]] = poz_in_heap[H[cp]];
                    poz_in_heap[H[cp]] = aux;
                    cp /= 2;
                }
            }
        }
        else
        {
            int cp = poz; bool este_heap = false;
            while((cp < lg && !este_heap) && H[2 * cp])
            {
                if(dist[H[2 * cp]] >= dist[H[cp]] && dist[H[2 * cp + 1]] >= dist[H[cp]])
                    este_heap = true;
                else
                {
                    if(dist[H[2 * cp]] < dist[H[2 * cp + 1]])
                    {
                        int aux = H[2 * cp];
                        H[2 * cp] = H[cp];
                        H[cp] = aux;

                        aux = poz_in_heap[H[2 * cp]];
                        poz_in_heap[H[2 * cp]] = poz_in_heap[H[cp]];
                        poz_in_heap[H[cp]] = aux;
                        cp *= 2;
                    }
                    else
                    {
                        int aux = H[2 * cp + 1];
                        H[2 * cp + 1] = H[cp];
                        H[cp] = aux;

                        aux = poz_in_heap[H[2 * cp + 1]];
                        poz_in_heap[H[2 * cp + 1]] = poz_in_heap[H[cp]];
                        poz_in_heap[H[cp]] = aux;
                        cp *= 2; cp++;
                    }
                }
            }
        }
    }
};

Heap heap;

void init()
{
    for(int i = 0; i <= N; i++)
        dist[i] = INFINIT;
}

void citire()
{
    fin >> N >> M;
    int x, y, cost;
    int cost_min = 1005;
    for(int i = 0; i < M; i++)
    {
        fin >> x >> y >> cost;
        pair < int, int > pair_1 = make_pair(y, cost);
        pair < int, int > pair_2 = make_pair(x, cost);
        costuri[x].push_back(pair_1);
        costuri[y].push_back(pair_2);
        if(cost < cost_min)
        {
            cost_min = cost;
            nod_start = x;
        }
    }
    init();
}

void Prim()
{
    for(unsigned int i = 0; i < costuri[nod_start].size(); i++)
    {
        tati[costuri[nod_start][i].first] = nod_start;
        dist[costuri[nod_start][i].first] = costuri[nod_start][i].second;
        heap.push(costuri[nod_start][i].first);
    }
    vizitat[nod_start] = 1;

    for(int i = 1; i <= N - 1; i++)
    {
        int mini = heap.pop();

        cost_minim += dist[mini];
        vizitat[mini] = 1;
        vx.push_back(tati[mini]); vy.push_back(mini);
        for(unsigned int k = 0; k < costuri[mini].size(); k++)
            if(costuri[mini][k].second < dist[costuri[mini][k].first])
                if(costuri[mini][k].first != nod_start && !vizitat[costuri[mini][k].first])
                {
                    tati[costuri[mini][k].first] = mini;
                    dist[costuri[mini][k].first] = costuri[mini][k].second;
                    if(poz_in_heap[costuri[mini][k].first])
                        heap.heapify(costuri[mini][k].first);
                    else
                        heap.push(costuri[mini][k].first);
                }
    }
}

void afisare()
{
    fout << cost_minim << '\n';
    fout << N - 1 << '\n';
    for(int i = 0; i < N - 1; i++)
        fout << vx[i] << ' ' << vy[i] << '\n';
}

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