#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

vector <PII> G[200002]; // Graful nostru {*nod vecin* , *costul muchiei*}
vector <PII> APM;       // APM-ul - stocheaza muchii {*nod* , *nod*}

priority_queue <PII, vector<PII>, greater<PII> > Q; // Heap {*cost* , *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({0, k});                             //introducem in coada nodul k, cu costul 0
    for (;!Q.empty();)
    {
        k = Q.top().y;                          //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 pentru nodul next.x putem sa scadem 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
                Q.push({next.y, 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().y])
            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
};