#include <bits/stdc++.h>
#include <iostream>

using namespace std;

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


vector<pair<int,int>>adiacenta[200000];//liste de perechi pt noduri pe adiacenta[i] vom avea perechea(j,cost) astfel incat exista muchie de la i la j cu costul cost
int n,m;//noduri, muchii
int total = 0;
priority_queue< pair<int,int>, vector <pair<int,int>>, greater<pair<int,int>> > pq; //coada de prioritati pt aflarea muchiei cu cost minim cu un nod in arbore si unul in afara
vector<int>vizitat;
vector <int> parinte;//vector in care constuiesc apm => parinte[i] = x => muchia i, x
vector <int> cost;//cost[i] = costul lui i in muchia din arbore i, parinte[i]


void Prim(int i)
{

    pq.push(make_pair(0, i));//inseram in coada de prioritati nodul de start, are costul 0 initial
    cost[i] = 0;
    //parinte[i] = -1;

    int varf;
    while (!pq.empty())
    {
        varf = pq.top().second; //luam varful cu costul del mai mic (coada prioritizeaza dupa primul element, adica costul)
        vizitat[varf] = true;



        pq.pop();

        for (pair<int,int> e : adiacenta[varf])//parcurgem vecinii nodului scos din coada
        {
            int vecin = e.first; //val vecinilui
            int c = e.second;//costu muhciei de la nodul scos la vecin

            if (!vizitat[vecin] && c < cost[vecin]) //daca vecinul nu este in abore si
            {
                ////si costul de la vecin la varf e mai mic decat costul curent al vecinului
                // Updatez vecinul

                cost[vecin] = c;
                pq.push(make_pair(cost[vecin], vecin));



                parinte[vecin] = varf; // muchie varf,vecin adaugata in arbore

            }

        }


    }


}


int main()
{
//spre de osebire de Kruskal porneste dintr-un no de start
//si adauga muchii plecand de la acesta facand un arbore partial
    in>>n>>m;
    int x,y,c;

    for(int i = 0; i<m ; i++)
    {
        in>>x>>y>>c;

        adiacenta[x-1].push_back(make_pair(y-1, c)); //graf neorientat
        adiacenta[y-1].push_back(make_pair(x-1, c));

    }

    vizitat.assign(n, false);
    cost.assign(n,10000);
    parinte.assign(n,-1);

    Prim(0);



    for(int i = 1; i <n; i++)
    {


        total+= cost[i];

    }
    out<<total<<"\n";

    out<<parinte.size() - 1<<"\n";

    for(int i = 1; i <n; i++)
    {


        out<<parinte[i] + 1<<" "<<i + 1<<"\n";

    }

///pt sparce grafuri(cu muhcii rare)
    ///in loc de cautare liniar se foloseste o coada de prioritati pt a determina muchia cu cost minim pt un nod care se afla in arbore si unul care nu se afla in arbore
    ///aflare minim => O(log n) + m acutalizari => O(m log n)

    return 0;
}