#include <bits/stdc++.h>

using namespace std;

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

const int infinity = numeric_limits<int>::max();
const int infinitytMin = numeric_limits<int>::min();

// muchie de la x la y cu costul cost
struct Muchie
{
    int x, y;
    int cost = 0;
    int capacitate = -1;
    int flux = -1;

    Muchie() = default;

    Muchie(int x, int y, int cost)
    {
        this->x = x;
        this->y = y;
        this->cost = cost;
    }

    Muchie(int x, int y)
    {
        this->x = x;
        this->y = y;
    }

    Muchie(int x, int y, int flux, int capacitate)
    {
        this->x = x;
        this->y = y;
        this->flux = flux;
        this->capacitate = capacitate;
    }
};

// nodul x are in lista de adiacenta un Nod cu nod=y si costul = 10
// daca avem muchie de la x la y cu costul 10
struct Nod
{
    int nod;
    int cost = 0;
    int capacitate = -1;
    int flux = -1;

    Nod() = default;
    Nod(int nod) { this->nod = nod; }
    Nod(int nod, int cost)
    {
        this->nod = nod;
        this->cost = cost;
    }

    Nod(int nod, int flux, int capacitate)
    {
        this->nod = nod;
        this->flux = flux;
        this->capacitate = capacitate;
    }
};

class Graf
{
public:
    int nrNoduri;
    int nrMuchii;
    vector<bool> vizitat;
    vector<int> grad_intern;
    vector<int> grad_extern;
    vector<vector<Nod>> lista_adiacenta;
    vector<Muchie> muchii;

    Graf() = default;

    Graf(int nrNoduri)
    {
        this->nrNoduri = nrNoduri;
        vizitat.resize(nrNoduri + 1);
        grad_intern.resize(nrNoduri + 1, 0);
        grad_extern.resize(nrNoduri + 1, 0);
        lista_adiacenta.resize(nrNoduri + 1);
    }
    Graf(int nrNoduri, int nrMuchii)
    {
        this->nrMuchii = nrMuchii;
        this->nrNoduri = nrNoduri;
        vizitat.resize(nrNoduri + 1);
        grad_intern.resize(nrNoduri + 1, 0);
        grad_extern.resize(nrNoduri + 1, 0);
        lista_adiacenta.resize(nrNoduri + 1);
    }
    void calculeazaGrad()
    {
        for (int nod = 1; nod <= nrNoduri; nod++)
            grad_extern[nod] = grad_intern[nod] = 0;
        for (int nod = 1; nod <= nrNoduri; nod++)
        {
            for (auto vecin : lista_adiacenta[nod])
            {
                grad_intern[vecin.nod] += 1;
                grad_extern[nod] += 1;
            }
        }
    }
    void dfs(int start, stack<int> &stiva)
    {
        vizitat[start] = true;
        for (auto vecin : lista_adiacenta[start])
        {
            if (vizitat[vecin.nod] == false)
            {
                dfs(vecin.nod, stiva);
            }
        }
        stiva.push(start);
    }

    void bfs(int start, vector<int> &tata)
    {
        queue<int> coada;
        coada.push(start);
        vizitat[start] = 1;
        while (!coada.empty())
        {
            int nod = coada.front();
            coada.pop();
            for (auto vecin : lista_adiacenta[nod])
            {
                if (vizitat[vecin.nod] == 0)
                {
                    coada.push(vecin.nod);
                    vizitat[vecin.nod] = 1;
                    tata[vecin.nod] = nod;
                }
            }
        }
    }

    vector<int> sortareTopologica()
    {
        vector<int> noduri_start;
        stack<int> stiva;
        for (int nod = 1; nod <= nrNoduri; nod++)
        {
            if (grad_intern[nod] == 0)
            {
                noduri_start.push_back(nod);
            }
        }

        for (auto nod : noduri_start)
        {
            dfs(nod, stiva);
        }

        vector<int> sortaretopologica;
        while (!stiva.empty())
        {
            sortaretopologica.push_back(stiva.top());
            stiva.pop();
        }

        return sortaretopologica;
    }

    void printGraf()
    {
        for (int i = 1; i <= nrNoduri; i++)
        {
            cout << i << ": ";
            for (auto nod : lista_adiacenta[i])
                cout << nod.nod << "(" << nod.cost << ") ";
            cout << endl;
        }
    }

    void printGrad()
    {
        for (int i = 1; i <= nrNoduri; i++)
        {
            cout << i << "-> grad intern = " << grad_intern[i] << ", grad extern = " << grad_extern[i] << endl;
        }
    }

    // drumul de cost maxim pentru graf orientat/neorientat aciclic de sursa si final unic
    // costul maxim  = drum[end]
    // drumul se obtine de la end pana ajungem la sursa prin vectorul de tati
    void drumCritic(int sursa, vector<int> &drum, vector<int> &tata)
    {
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = -1;
            tata[i] = 0;
        }
        drum[sursa] = 0;
        vector<int> top = sortareTopologica();
        for (auto nod : top)
        {
            for (auto vecin : lista_adiacenta[nod])
            {
                if (drum[nod] + vecin.cost > drum[vecin.nod])
                {
                    drum[vecin.nod] = drum[nod] + vecin.cost;
                    tata[vecin.nod] = nod;
                }
            }
        }
    }

    void Djikstra(int sursa, vector<int> &drum, vector<int> &tata)
    {
        drum.clear();
        tata.clear();
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = infinity;
            tata[i] = 0;
        }
        drum[sursa] = 0;

        auto cmp = [&](int nod1, int nod2)
        { return drum[nod1] > drum[nod2]; };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

        // daca am adaugat o sursa imaginara si doresc sa pornesc din locuri multiple :
        // for (int i = 1; i <= nrNoduri; i++)
        //     pq.push(i);

        pq.push(sursa);
        while (!pq.empty())
        {
            int nod = pq.top();
            pq.pop();

            for (auto vecin : lista_adiacenta[nod])
            {
                if (drum[nod] + vecin.cost < drum[vecin.nod])
                {
                    drum[vecin.nod] = drum[nod] + vecin.cost;
                    pq.push(vecin.nod);
                    tata[vecin.nod] = nod;
                }
            }
        }
    }

    // intoarce false daca contine circuit negativ, true daca nu
    bool BellmanFord(int sursa, vector<int> &drum, vector<int> &tata, int &negativStart)
    {
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = infinity;
            tata[i] = 0;
        }
        drum[sursa] = 0;
        for (int k = 1; k <= nrNoduri - 1; k++)
        {
            for (auto muchie : muchii)
            {
                if (drum[muchie.x] < infinity && drum[muchie.x] + muchie.cost < drum[muchie.y])
                {
                    drum[muchie.y] = drum[muchie.x] + muchie.cost;
                    tata[muchie.y] = muchie.x;
                }
            }
        }
        // a n a rulare a algoritmului pentru a detecta ciclul negativ
        for (auto muchie : muchii)
        {
            if (drum[muchie.x] < infinity && drum[muchie.x] + muchie.cost < drum[muchie.y])
            {
                drum[muchie.y] = drum[muchie.x] + muchie.cost;
                tata[muchie.y] = muchie.x;
                negativStart = muchie.y;
                return false;
            }
        }
        return true;
    }

    // BellmanFord cu queue -> mai rapid decat primul si da 100% pe toate cazurile pe infoarena
    bool BellmanFordQueue(int sursa, vector<int> &drum, vector<int> &tata, int &negativStart)
    {
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = infinity;
            tata[i] = 0;
        }
        drum[sursa] = 0;
        vector<bool> inQueue(nrNoduri + 1, false);
        queue<int> q;
        q.push(sursa);
        inQueue[sursa] = true;
        vector<int> lungime(nrNoduri + 1, 0);
        while (!q.empty())
        {
            int nod = q.front();
            q.pop();
            inQueue[nod] = false;
            for (auto vecin : lista_adiacenta[nod])
            {
                if (drum[nod] < infinity && drum[nod] + vecin.cost < drum[vecin.nod])
                {
                    drum[vecin.nod] = drum[nod] + vecin.cost;
                    tata[vecin.nod] = nod;
                    if (inQueue[vecin.nod] == false)
                    {
                        q.push(vecin.nod);
                        inQueue[vecin.nod] = true;
                    }
                    lungime[vecin.nod] = lungime[nod] + 1;
                    if (lungime[vecin.nod] > nrNoduri - 1)
                    {
                        negativStart = vecin.nod;
                        return false;
                    }
                }
            }
        }
        return true;
    }

    void afisareDrum(int start, int end, vector<int> tata)
    {
        // cout << start << " " << end << endl;
        // for (int i = 1; i <= nrNoduri; i++)
        //     cout << tata[i] << " ";
        // cout << endl;
        vector<int> drum;
        if (start != end) // daca e circuit nu trebuie sa punem finalul de 2 ori
            drum.push_back(end);
        while (tata[end] != start)
        {
            end = tata[end];
            drum.push_back(end);
        }
        drum.push_back(start);
        for (int i = drum.size() - 1; i >= 0; i--)
            cout << drum[i] << " ";
    }

    // daca dupa algoritm avem drumuri[i][i] < 0 pentru un i => circuit negativ
    // am decis ca daca nu exista drum atunci in matrice e 0
    // de asemenea drumuri[i][i] = lantul minim folosin cel putin un arc sau infinit daca nu exista un
    // lant de lungime nevida de la i la i ( circuit practic )
    void FloydWarshall(vector<vector<int>> &drumuri, vector<vector<int>> &predecesor)
    {
        drumuri.resize(nrNoduri + 1);
        predecesor.resize(nrNoduri + 1);
        for (int nod = 1; nod <= nrNoduri; nod++)
        {
            drumuri[nod].resize(nrNoduri + 1, infinity);
            predecesor[nod].resize(nrNoduri + 1, 0);
            for (auto vecin : lista_adiacenta[nod])
            {
                drumuri[nod][vecin.nod] = vecin.cost;
                predecesor[nod][vecin.nod] = nod;
            }
        }
        // for (int i = 1; i <= nrNoduri; i++)
        //     drumuri[i][i] = 0;
        for (int k = 1; k <= nrNoduri; k++)
        {
            for (int i = 1; i <= nrNoduri; i++)
            {
                for (int j = 1; j <= nrNoduri; j++)
                {
                    if (drumuri[i][k] < infinity && drumuri[k][j] < infinity)
                    {
                        if (drumuri[i][j] > drumuri[i][k] + drumuri[k][j])
                        {
                            drumuri[i][j] = drumuri[i][k] + drumuri[k][j];
                            predecesor[i][j] = predecesor[k][j];
                        }
                    }
                }
            }
        }

        for (int i = 1; i <= nrNoduri; i++)
        {
            for (int j = 1; j <= nrNoduri; j++)
            {
                if (drumuri[i][j] == infinity)
                    drumuri[i][j] = 0; // nu exista drum
            }
        }
    }

    void drumMat(int x, int y, vector<vector<int>> predecesor)
    {
        if (x != y)
            drumMat(x, predecesor[x][y], predecesor);
        cout << y << " ";
    }

    void afisCircuitMat(int x, int y, vector<vector<int>> predecesor)
    {
        if (predecesor[x][y] != x)
            afisCircuitMat(x, predecesor[x][y], predecesor);
        cout << y << " ";
    }

    void afisareDrumuriMat(vector<vector<int>> drumuri, vector<vector<int>> predecesor)
    {
        for (int i = 1; i <= nrNoduri; i++)
        {
            cout << i << ": \n";
            for (int j = 1; j <= nrNoduri; j++)
            {
                cout << "       " << j << ": ";
                if (drumuri[i][j] == 0)
                    cout << "nu exista drum\n";
                else
                {
                    drumMat(i, j, predecesor);
                    cout << " cu costul: " << drumuri[i][j] << endl;
                }
            }
        }
    }

    long long Prim(int start, vector<Muchie> &muchiiApcm)
    {
        vector<int> d(nrNoduri + 1, infinity);
        vector<int> tata(nrNoduri + 1, -1);
        vector<bool> inHeap(nrNoduri + 1, true);

        auto cmp = [&](int nod1, int nod2)
        { return d[nod1] > d[nod2]; };
        priority_queue<int, vector<int>, decltype(cmp)> minHeap(cmp);

        d[start] = 0;
        minHeap.push(start);

        while (!minHeap.empty())
        {

            int u = minHeap.top();
            minHeap.pop();
            inHeap[u] = false;

            for (auto vecin : lista_adiacenta[u])
            {
                if (inHeap[vecin.nod] && vecin.cost < d[vecin.nod])
                {
                    d[vecin.nod] = vecin.cost;
                    tata[vecin.nod] = u;
                    minHeap.push(vecin.nod);
                }
            }
        }
        long long cost = 0;
        for (int i = 1; i <= nrNoduri; i++)
            if (i != start)
            {
                muchiiApcm.push_back(Muchie(i, tata[i]));
                cost += d[i];
            }
        return cost;
    }
};

void iterativeDFS(int start, vector<vector<int>> la, vector<int> &tati)
{
    int n = la.size() - 1;
    vector<bool> vizitat(n + 1, false);
    stack<int> stack;
    stack.push(start);

    while (!stack.empty())
    {
        int nod = stack.top();
        stack.pop();

        if (vizitat[nod] == false)
        {
            cout << nod;
            vizitat[nod] = true;
        }

        for (auto vecin : la[nod])
            if (vizitat[vecin] == false)
                stack.push(vecin);
    }
}

int main()

{
    int n, m;
    in >> n >> m;
    Graf g(n, m);
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        g.lista_adiacenta[x].push_back(Nod(y, c));
        g.lista_adiacenta[y].push_back(Nod(x, c));
        g.muchii.push_back(Muchie(x, y, c));
    }
    vector<Muchie> muchiiApcm;
    long long cost = g.Prim(1, muchiiApcm);

    out << cost << "\n";
    out << n - 1 << endl;
    for (auto m : muchiiApcm)
        out << m.x << " " << m.y << endl;

    return 0;
}