#include <bits/stdc++.h>

using namespace std;

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

const int MAX = 200001;

class Graf
{
    int NrNoduri;

public:

    Graf(int NrNoduri);

    void Apm(int nod, vector <pair<int, int>> G[MAX]);
};

Graf::Graf(int NrNoduri)
{
    this->NrNoduri = NrNoduri;
}

void Graf::Apm(int nod, vector <pair<int, int>> G[MAX])
{
    priority_queue <pair<int, int>, vector<pair <int, int>>, greater<pair<int,int>>> Coada;
    bool Vizitat[MAX] = {0};
    int distanta[MAX];
    int Tcost = 0;
    vector <int> tata(MAX);
    vector <pair<int, int>> arbore;

    for(int i = 1; i <= NrNoduri; i++)
        distanta[i] = INT_MAX;

    distanta[nod] = 0;
    Coada.push(make_pair(0, nod));

    while(!Coada.empty())
    {
        int nodcurent = Coada.top().second;
        Coada.pop();

        if(!Vizitat[nodcurent])
        {
            Vizitat[nodcurent] = 1;
            Tcost += distanta[nodcurent];

            if(tata[nodcurent] > 0)
                arbore.push_back(make_pair(nodcurent, tata[nodcurent]));

            for(int i = 0; i < G[nodcurent].size(); i++)
            {
                int Vecin = G[nodcurent][i].first;
                int Cost = G[nodcurent][i].second;


                if(!Vizitat[Vecin] && distanta[Vecin] > Cost)
                {
                    distanta[Vecin] = Cost;
                    tata[Vecin] = nodcurent;
                    Coada.push(make_pair(distanta[Vecin], Vecin));
                }
            }
        }
    }

    out << Tcost << "\n" << arbore.size() << "\n";
    for(int i = 0; i < arbore.size(); i++)
        out << arbore[i].first << " " << arbore[i].second << "\n";
}

int main()
{
    int N, M;
    in >> N >> M;

    Graf g(N);
    int nod1, nod2, cost;
    vector <pair<int, int>>G[MAX];

    for(int i = 0; i < M; i++)
    {
        in >> nod1 >> nod2 >> cost;
        G[nod1].push_back(make_pair(nod2, cost));
        G[nod2].push_back(make_pair(nod1, cost));
    }

    g.Apm(1, G);
    return 0;
}