#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
 
using namespace std;

class Graf
{
private:
    static constexpr int NMAX = 100009;
    const int N, M;
    vector<int> Adiacenta[NMAX];  // liste de adiacenta

public:
    Graf(int, int);
    void AdMuchie(int, int);

    static constexpr int getNMAX() { return Graf::NMAX; }

public:
    void Bfs(int, int*);
    int Dfs();
    void Biconex(vector<vector<int>>&);
    void CompTareConexe(vector<int>*, vector<vector<int>>&, int&);
    void MuchieCritica(vector<vector<int>>&);
    void ProbGraf_NoduriComune(int, int, vector<int>&);
    void SortTopo(int*);

    static bool HavelHakimi(int*, int);

public:
    void APM(vector<vector<int>>&, int&, vector<pair<int, int>>&); 
    
    static void Disjoint(int, vector<vector<int>>&, vector<string>&);

private:
    void Dfs_fHelper(int, bool*);
    void Biconex_fHelper(int, int, pair<int, int>*, int&, int*, int*, vector<vector<int>>&);
    void CompTareConexe_Dfs(int, bool*, int*, int&);
    void CompTareConexe_t_Dfs(int, bool*, vector<int>*, vector<vector<int>>&, int);
    void MuchieCritica_fHelper(int, int, int*, int*, vector<vector<int>>&);
    void NoduriComune_BfsInainte(int, int, int*);
    void NoduriComune_BfsInapoi(int, int, int*, int*, vector<int>&);

    static int Disjoint_CautaRadacina(int, int*);
    static void Disjoint_CompresieDrumuri(int, int, int*);
    static void Disjoint_Reuneste(int, int, int*, int*);
};
 
Graf::Graf(int n, int m)
    : N(n), M(m)
{
}
 
void Graf::AdMuchie(int ini, int fin)
{
    Adiacenta[ini].push_back(fin);
}

void Graf::Bfs(int S, int* nrArce)
{
    int coada[NMAX], st = 0, dr = 0;
 
    for (int i = 1; i <= N; ++i)
        nrArce[i] = -1;
    nrArce[S] = 0;
    coada[st] = S;
    while (st <= dr)
    {
        int curent = coada[st++];
        for (auto it = Adiacenta[curent].begin(); it != Adiacenta[curent].end(); ++it)
            if(nrArce[*it] == -1)
            {
                coada[++dr] = *it;
                nrArce[*it] = nrArce[curent] + 1;
            }
    }
}

int Graf::Dfs()
{
    bool vizitat[NMAX];
    int nrComp = 0;

    memset(vizitat, 0, NMAX * sizeof(bool));
    for (int i = 1; i <= N; ++i)
        if (!vizitat[i])
        {
            ++nrComp;
            Dfs_fHelper(i, vizitat);
        }

    return nrComp;
}

void Graf::Dfs_fHelper(int curent, bool* vizitat)
{
    vizitat[curent] = true;
    for (auto it = Adiacenta[curent].begin(); it != Adiacenta[curent].end(); ++it)
        if (!vizitat[*it])
            Dfs_fHelper(*it, vizitat);
}

void Graf::Biconex(vector<vector<int>>& compBic)
{
    pair<int, int> Stiva[NMAX * 2];
    int stVf = 0;
    int nivelInArbDFS[NMAX];  // folosit si ca vizitat[]
    int nivelMinVecini[NMAX];

    nivelInArbDFS[0] = 0;
    Biconex_fHelper(1, 0, Stiva, stVf, nivelInArbDFS, nivelMinVecini, compBic);
}

void Graf::Biconex_fHelper(int nod, int parinte, pair<int, int>* Stiva, int& stVf, int* nivelInArbDFS, int* nivelMinVecini, vector<vector<int>>& compBic)
{
    nivelInArbDFS[nod] = nivelInArbDFS[parinte] + 1;
    nivelMinVecini[nod] = NMAX;
    for (int& vecin : Adiacenta[nod])
    {
        if (nivelInArbDFS[vecin])  // daca e vizitat
        {
            if (nivelMinVecini[nod] > nivelInArbDFS[vecin] && vecin != parinte)
                nivelMinVecini[nod] = nivelInArbDFS[vecin];
        }
        else
        {
            Stiva[++stVf] = {nod, vecin};
            Biconex_fHelper(vecin, nod, Stiva, stVf, nivelInArbDFS, nivelMinVecini, compBic);

            if (nivelMinVecini[nod] > nivelMinVecini[vecin])
                nivelMinVecini[nod] = nivelMinVecini[vecin];
            
            if (nivelMinVecini[vecin] >= nivelInArbDFS[nod])
            {
                compBic.push_back({});
                while (Stiva[stVf].first != nod)
                    compBic.back().push_back(Stiva[stVf--].second);
                compBic.back().push_back(Stiva[stVf].second);  // muchia din 'nod', intreaga
                compBic.back().push_back(Stiva[stVf].first);   //
                --stVf;
            }
        }
    }
}

void Graf::CompTareConexe(vector<int>* t_Adiacenta, vector<vector<int>>& compTC, int& nrComp)
{
    int stivaTopo[NMAX], stVf = 0;    // stivaTopo - stiva de noduri in care nodurile sunt inserate in ordinea topologica inversata
    bool vizitat[NMAX];

    memset(vizitat, 0, (N + 1) * sizeof(bool));
    for (int nod = 1; nod <= N; ++nod)
        if (!vizitat[nod])
            CompTareConexe_Dfs(nod, vizitat, stivaTopo, stVf);

    compTC.resize(N);
    nrComp = 0;
    memset(vizitat, 0, (N + 1) * sizeof(bool));
    while (stVf)
    {
        if (!vizitat[stivaTopo[stVf]])
            CompTareConexe_t_Dfs(stivaTopo[stVf], vizitat, t_Adiacenta, compTC, nrComp++);
        --stVf;
    }
}

void Graf::CompTareConexe_Dfs(int nod, bool* vizitat, int* stivaTopo, int& stVf)
{
    vizitat[nod] = true;
    for (auto& vecin : Adiacenta[nod])
        if (!vizitat[vecin])
            CompTareConexe_Dfs(vecin, vizitat, stivaTopo, stVf);
    stivaTopo[++stVf] = nod; 
}

void Graf::CompTareConexe_t_Dfs(int nod, bool* vizitat, vector<int>* t_Adiacenta, vector<vector<int>>& compTC, int nrComp)
{
    vizitat[nod] = true;
    for (auto& vecin : t_Adiacenta[nod])
        if (!vizitat[vecin])
            CompTareConexe_t_Dfs(vecin, vizitat, t_Adiacenta, compTC, nrComp);
    compTC[nrComp].push_back(nod);
}

void Graf::MuchieCritica(vector<vector<int>>& mCritice)
{
    int nivelInArbDFS[NMAX];  // folosit si ca vizitat[]
    int nivelMin[NMAX];

    memset(nivelInArbDFS, 0, (N + 1) * sizeof(int));
    MuchieCritica_fHelper(0, 0, nivelInArbDFS, nivelMin, mCritice);
}

void Graf::MuchieCritica_fHelper(int nod, int parinte, int* nivelInArbDFS, int* nivelMin, vector<vector<int>>& mCritice)
{
    nivelInArbDFS[nod] = nivelMin[nod] = nivelInArbDFS[parinte] + 1;
    for (int& vecin : Adiacenta[nod])
    {
        if (nivelInArbDFS[vecin])
        {
            if (nivelMin[nod] > nivelInArbDFS[vecin] && vecin != parinte)
                nivelMin[nod] = nivelInArbDFS[vecin];
        }
        else
        {
            MuchieCritica_fHelper(vecin, nod, nivelInArbDFS, nivelMin, mCritice);

            if (nivelMin[nod] > nivelMin[vecin])
                nivelMin[nod] = nivelMin[vecin];

            // muchie critica
            if (nivelMin[vecin] > nivelInArbDFS[nod])  // nivelMin[vecin] == nivelInArbDFS[vecin]
                mCritice.push_back({nod, vecin});
        }
    }
}

void Graf::ProbGraf_NoduriComune(int X, int Y, vector<int>& noduri)
{
    int lungime[NMAX];  // folosit si ca vizitat[] in BfsInainte => lungimea se calculeaza incepand de la 1
    int nrVizite[NMAX];  // folosit in BfsInapoi pt a identifica unificarea ramurilor (si pentru vizitat[])

    noduri.push_back(X);
    // noduri.push_back(Y);  -- nu e nevoie, e mereu primul adaugat in BfsInapoi
    NoduriComune_BfsInainte(X, Y, lungime);
    NoduriComune_BfsInapoi(X, Y, lungime, nrVizite, noduri);

    sort(noduri.begin(), noduri.end());
}

void Graf::NoduriComune_BfsInainte(int X, int Y, int* lungime)
{
    int coada[NMAX], st = 0, dr = -1;
    bool COADA_STOP_INTRARI = false;

    coada[++dr] = X;
    lungime[X] = 1;
    while (st <= dr)
    {
        int nodCurent = coada[st++];
        for (int& vecin : Adiacenta[nodCurent])
            if (!lungime[vecin])
            {
                lungime[vecin] = lungime[nodCurent] + 1;
                if (vecin == Y)
                    COADA_STOP_INTRARI = true;
                if (!COADA_STOP_INTRARI)
                    coada[++dr] = vecin;
            }
    }
}

void Graf::NoduriComune_BfsInapoi(int X, int Y, int* lungime, int* nrVizite, vector<int>& noduri)
{
    int nrRamuri = 1;   // total ramuri existente la pasul curent

    int coada[NMAX], st = 0, dr = -1;
    coada[++dr] = Y;
    while (st <= dr)
    {
        int nodCurent = coada[st++];
        int ramuriDinCurent = 0;      // cate ramuri pornesc din nodul curent, cel putin una din moment ce avem drum mai departe

        if (nrRamuri == 1)
            noduri.push_back(nodCurent);

        for (int& vecin : Adiacenta[nodCurent])
        {
            if (lungime[vecin] == lungime[nodCurent] - 1)
            {
                ++ramuriDinCurent;
                ++nrVizite[vecin];
                if (nrVizite[vecin] > 1)
                    --nrRamuri;
                if (vecin == X)
                    break;
                if (nrVizite[vecin] == 1)
                    coada[++dr] = vecin;
            }
        }

        nrRamuri += (ramuriDinCurent - 1); 
    }                                 
}

void Graf::SortTopo(int* noduri)
{
    bool vizitat[NMAX];
    int dr = 0;
    
    memset(vizitat, 0, (N + 1) * sizeof(bool));
    for (int nod = 1; nod <= N; ++nod)
        if (!vizitat[nod])
            CompTareConexe_Dfs(nod, vizitat, noduri, dr);
    reverse(noduri + 1, noduri + 1 + N);
}

bool Graf::HavelHakimi(int* S, int N)
{
    auto descrescator = [](int a, int b) { return a > b; };
    sort(S, S + N, descrescator);

    if (S[0] >= N)
        return false;
    
    int grMax, pozPrimElem = 0;
    while (S[pozPrimElem] > 0)
    {   
        grMax = S[pozPrimElem++];
        for (int i = pozPrimElem; i < pozPrimElem + grMax; ++i)
            --S[i];

        sort(S + pozPrimElem, S + N, descrescator);
        if (S[N - 1] < 0)
            return false;
    }
    return true;
}

void Graf::APM(vector<vector<int>>& muchiiGraf, int& costAPM, vector<pair<int, int>>& muchiiAPM)
{
    auto comp = [](vector<int>& m1, vector<int>& m2) { return m1[2] < m2[2]; };
    sort(muchiiGraf.begin(), muchiiGraf.end(), comp);
    costAPM = 0;
    muchiiAPM.reserve(N - 1);

    int tata[NMAX * 2], rang[NMAX * 2];  // rangurile arborilor se retin in radacini
    memset(tata, 0, N * sizeof(int));
    memset(rang, 0, N * sizeof(int));  // va fi inaltime - 1

    auto mc = muchiiGraf.begin();
    while (muchiiAPM.size() < N - 1)
    {
        int x = mc->at(0);
        int y = mc->at(1);
        int cost = mc->at(2);
        int radX = Disjoint_CautaRadacina(x, tata);
        int radY = Disjoint_CautaRadacina(y, tata);
        Disjoint_CompresieDrumuri(x, radX, tata);
        Disjoint_CompresieDrumuri(y, radY, tata);

        if (radX != radY)
        {
            Disjoint_Reuneste(radX, radY, tata, rang);

            costAPM += cost;
            muchiiAPM.push_back({x, y});
        }

        ++mc;
    }
}

int Graf::Disjoint_CautaRadacina(int nod, int* tata)
{
    while (tata[nod])
        nod = tata[nod];
    return nod;
}

void Graf::Disjoint_CompresieDrumuri(int nod, int radacina, int* tata)
{
    while (tata[nod])
    {
        int old = tata[nod];
        tata[nod] = radacina;
        nod = tata[old];
    }
}

void Graf::Disjoint_Reuneste(int radX, int radY, int* tata, int* rang)
{
    if (rang[radX] > rang[radY])  // fiindca rang[radX] e strict mai mare decat rang[radY], 
        tata[radY] = radX;        // adaugarea arb. radY ca subarb. al lui radX nu va putea creste rang[radX]
    else // rang[radX] <= rang[radY]
    {
        tata[radX] = radY;
        if (rang[radY] == rang[radX])   // daca rangurile sunt egale, prin legarea rad., rangul celui de care s-a legat va creste cu 1
            ++rang[radY];
    }
}
void Graf::Disjoint(int N, vector<vector<int>>& Operatii, vector<string>& Raspuns)
{
    int tata[NMAX], rang[NMAX];  // rangurile arborilor se retin in radacini
    memset(tata, 0, N * sizeof(int));
    memset(rang, 0, N * sizeof(int));  // va fi inaltime - 1

    for (auto& op : Operatii)
    {
        int x = op[1];
        int y = op[2];
        int radX = Disjoint_CautaRadacina(x, tata);
        int radY = Disjoint_CautaRadacina(y, tata); 

        if (op[0] == 1)
            Disjoint_Reuneste(radX, radY, tata, rang);
        else
        {
            if (radX != radY)
                Raspuns.emplace_back("NU");
            else
                Raspuns.emplace_back("DA");

            // Compresia drumurilor
            Disjoint_CompresieDrumuri(x, radX, tata);
            Disjoint_CompresieDrumuri(y, radY, tata);
        }
    }
}
#include <iostream>
int main()
{   
    ifstream f("apm.in");
    ofstream g("apm.out");
    int N, M;
    
    f >> N >> M;
    Graf graf(N, M);
    vector<vector<int>> muchiiGraf;
    muchiiGraf.reserve(M);
    for(int x, y, c, i = 0; i < M; ++i)
    {
        f >> x >> y >> c;
        muchiiGraf.push_back({x, y, c});
    }

    int costAPM;
    vector<pair<int, int>> muchiiAPM;
    graf.APM(muchiiGraf, costAPM, muchiiAPM);

    g << costAPM << '\n';
    g << N - 1 << '\n';
    for (auto& mc : muchiiAPM)
        g << mc.first << ' ' << mc.second << '\n';

    return 0;
}