#include <iostream>
#include <vector>
#include <fstream>
#include <queue>

using namespace std;

ifstream f("date.in");
ofstream g("date.out");

struct legatura{
    int cost, destinatie;
};

struct nod{
    int cost, vizitat, precedent;
    vector <legatura> legaturi;
};



int main()
{
    vector <nod> noduri;
    int i, n, m, X, Y, C;

    f>>n>>m;

    for (i = 0; i < n; i++)
    {
        nod nou;
        nou.cost = 0;
        nou.vizitat = 0;
        nou.precedent = 0;
        noduri.push_back(nou);
    }

    for (i = 0; i < m; i++)
    {
        f>>X>>Y>>C;
        X--;
        Y--;

        legatura noua;
        noua.destinatie = Y;
        noua.cost = C;

        noduri[X].legaturi.push_back(noua);
    }

    vector <int> coada;

    coada.push_back(0);
    noduri[0].vizitat = 1;

    while(!coada.empty())
    {
        int indCoada = 0;
        for (i = 1; i < coada.size(); i++)
            if (noduri[coada[indCoada]].cost > noduri[coada[i]].cost)
                indCoada = i;

        int nodCurent = coada[indCoada];
        int costNod = noduri[nodCurent].cost;
        coada.erase(coada.begin() + indCoada);

        for (i = 0; i < noduri[nodCurent].legaturi.size(); i++)
        {
            int nodDestinatie = noduri[nodCurent].legaturi[i].destinatie;
            int costTotal = costNod + noduri[nodCurent].legaturi[i].cost;
            if (costTotal < noduri[nodDestinatie].cost || noduri[nodDestinatie].vizitat == 0)
            {
                noduri[nodDestinatie].cost = costTotal;
                noduri[nodDestinatie].vizitat = 1;
                noduri[nodDestinatie].precedent = nodCurent;
                coada.push_back(nodDestinatie);
            }
        }
    }

    int total = 0;
    int nrNoduri = 0;

    for (i = 0; i < n; i++)
        if (noduri[i].vizitat == 1)
        {
            total += noduri[i].cost;
            nrNoduri++;
        }

    g<<total<<endl<<nrNoduri - 1<<endl;
    for (i = 0; i < n; i++)
        if (noduri[i].vizitat == 1 && noduri[i].precedent != i)
            g<<noduri[i].precedent+1<<" "<<i+1<<endl;

    return 0;
}