#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define PII pair<int,int>
#define x first
#define y second

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

int N, M;
int D[200002];          // D[i] = Costul de intrare in nodul i (se initializeaza cu INF, apoi se minimizeaza)
int T[200002];          // T[i] = tata nodului i in APM
int APMCOST;            // Costul tuturor muchilor
bool B[200002];         // B[i] = 0 inseamna ca nodul i NU a fost vizitat
bool InQueue[200002];   // InQueue[i] = 0 inseamna ca nodul i NU e in coada
vector <PII> G[200002]; // Graful nostru {*nod vecin* , *costul muchiei*}
vector <PII> APM;       // APM-ul - stocheaza muchii {*nod* , *nod*}

struct CMP{
    bool operator ()(int a, int b)
    {
        return D[a]>D[b];
    }
};

priority_queue <int, vector<int>, CMP > Q; // Heap (*nod*)

void Prim(int k);

int main()
{
    is >> N >> M;
    for (int i = 1, a, b, c; i <= M; ++i)
    {
        is >> a >> b >> c;                  //
        G[a].push_back({b, c});             //citire
        G[b].push_back({a, c});             //
    }
    Prim(1);                               ///REZOLVARE
    is.close();
    is.close();
}

void Prim(int k)
{
    for (int i = 1; i <= N; ++i) D[i] = 1<<25;  //initializam cu INF
    D[k] = 0;                                   //nodul de pornire are costul 0!
    Q.push(k);                                  //introducem in coada nodul k, cu costul 0
    for (;!Q.empty();)
    {
        k = Q.top();                            //luam nodul cu costul cel mai mic
        B[k] = 1;                               //marcam nodul (nu-l vom mai parcurge, deoarece stim sigur ca are cost minim!)
        for (const auto& next : G[k])
        {
            if (B[next.x])                      //continuam ptr ca nodul next.x e deja in APM
                continue;                       //si costul lui este deja minim

            if (D[next.x] > next.y &&           //daca nodul next.x este in coada
                InQueue[next.x] == 1)           //si daca ii putem scadea costul
            {
                D[next.x] = next.y;             //... o facem
                T[next.x] = k;                  //retinem tatal lui next.x (in caz ca ne trebuie muchiile APM-ului
            }                                   //nu introducem acelasi nod de 2 ori in coada

            if (D[next.x] > next.y              //daca nodul next.x nu este in coada si daca
                && InQueue[next.x] == 0)        //putem sa-i scadem costul
            {
                D[next.x] = next.y;             //... o facem
                InQueue[next.x] = 1;
                T[next.x] = k;                  //retinem tatal lui next.x (in caz ca ne trebuie muchiile APM-ului
                Q.push(next.x);                 //introducem nodul next.x in coada, cu un cost nou, posibil mai mic
            }
        }
        APM.push_back({T[k], k});               //adaugam muchia dintre k si tatal sau la APM
        APMCOST += D[k];                        //updatam costul APM-ului
        while (!Q.empty() && B[Q.top()])
            InQueue[Q.top()] = 1, Q.pop();      //dam afara din heap nodurile care sunt in APM deja
    }
    os << APMCOST << '\n' << APM.size()-1 << '\n';  //afisam costul, numarul de muchii ale APM-ului
    for (int i = 1; i < APM.size(); ++i)
        os << APM[i].x << ' ' << APM[i].y << '\n';  //si muchile
};