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

using namespace std;

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

const int nmax = 200001;
const int inf = (1<<30);

class Graf
{
private:
    bool orientat;
    int nrNoduri;
    vector <int> listaAdiacenta[nmax];
    vector <pair <int, int>> listaAdiacentaCost[nmax];
public:
    Graf(int nrNoduri = 0, bool orientat = false);
    void adaugaMuchieCost(int, int, int);
    void citireMuchii(int);
    void citireMuchiiCost(int);
    vector<int> BFS(int);
    void DFS(int, bool*);
    int nrComponenteConexe();
    void DFSStiva(int nodcurent, bool *, stack<int> &);
    void sortareTopologica();
    void TarjanCTC(int&, int, int*, int*, bool*, stack <int> &, vector<vector<int>> &);
    void CTC();
    void TarjanBC(int&, int, int, int*, int*, stack <int>&, vector<vector<int>>&);
    void BC();
    void TarjanMC(int&, int, int, int*, int*, vector<pair<int,int>>&);
    void MC();
    vector <int> citireHakimi();
    bool Hakimi(vector <int>);
    vector <int> Dijkstra(int);
    pair<int, vector <pair <int, int>>> Prim(int);
};

Graf :: Graf(int nrNoduri, bool orientat) : nrNoduri(nrNoduri), orientat(orientat)
{
    this->nrNoduri = nrNoduri;
    this->orientat = orientat;
}

void Graf::adaugaMuchieCost(int nod1, int nod2, int cost)
{
    listaAdiacentaCost[nod1].push_back(make_pair(nod2, cost));
}

void Graf::citireMuchiiCost(int nrMuchii)
{
    int nod1, nod2, cost;
    for(int i = 0; i < nrMuchii; i++)
    {
        in >> nod1 >> nod2 >> cost;
        adaugaMuchieCost(nod1, nod2, cost);
        if(!orientat)
        {
            adaugaMuchieCost(nod2, nod1, cost);
        }
    }
}

pair<int, vector <pair <int, int>>> Graf::Prim(int nodStart)
{
    vector <pair <int, int>> rezultat;
    vector <int> cost(nmax);
    fill(cost.begin(), cost.end(), inf);
    priority_queue <pair <int, int>, vector <pair <int, int>>, greater<pair<int,int>>> coada;
    bool vizitat[nmax] = {0};
    int costTotal = 0;
    vector<int> parinte(nmax);
    cost[nodStart] = 0;
    coada.push(make_pair(0,nodStart));
    while(!coada.empty())
    {
        int nodCurent = coada.top().second;
        coada.pop();
        if(!vizitat[nodCurent])
        {
            vizitat[nodCurent] = true;
            costTotal += cost[nodCurent];
            if(parinte[nodCurent] > 0)
            {
                rezultat.push_back(make_pair(nodCurent, parinte[nodCurent]));
            }
            for (auto vecin:listaAdiacentaCost[nodCurent]) {
                if (!vizitat[vecin.first]) {
                    if (vecin.second < cost[vecin.first]) {
                        cost[vecin.first] = vecin.second;
                        parinte[vecin.first] = nodCurent;
                        coada.push(make_pair(cost[vecin.first], vecin.first));
                    }
                }
            }
        }
    }
    return make_pair(costTotal, rezultat);
}

int main()
{
    int n, m;
    in >> n >> m;
    Graf g(n,false);
    g.citireMuchiiCost(m);
    pair <int, vector <pair <int, int>>> rezultat;
    rezultat = g.Prim(1);
    out << rezultat.first << "\n";
    out << rezultat.second.size() << "\n";
    for(int i = 0; i < rezultat.second.size(); i++)
    {
        out << rezultat.second[i].first << " " << rezultat.second[i].second << '\n';
    }
    return 0;
}