#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int N = 200001;


/// PRIM - coada de prioritati pentru muchii - tot dupa cost -

/// incep cu un arbore care contine doar nodul 1
/// adaug in coada de prioritati doar muchiile din 1
/// sa presupunem ca am ajuns la un pas al algoritmului si avem o multime de varfuri adaugate la APM
/// in coada de prioritati voi avea doar muchii incidente la varfurile deja puse
/// dintre acestea, pentru a creste APM-ul cu un varf aleg cea mai mica muchie care
/// are un capat pus si unul nepus in APM <aceasta mchie sigur este deja in coada de prioritati>
/// cand aleg acea muchie x-y cu x pus si y nepus
/// completez coada de prioritati cu muchii care pleaca din y
/// trucul este ca muchiile y-z cu z pus nu mai sunt necesare deci pe alea nu le adaug in coada de prioritati
/// cand numarul de muchii a devenit n-1 <=> numarul de noduri puse a devenit n am terminat !!!



bitset<N> used;
priority_queue<tuple<int,int,int>> pq;/// vectorul muchiilor
int n,m,costAPM;/// T[] sirul de tati pentru DSU
vector<pair<int,int>> sol;/// sirul care va memora muchiile folosite in APM
vector<pair<int,int>> v[N];/// listele de vecin: un vecin este o pereche (x,c) unde x este vecinul si c este costul muchiei
void addEdges(int nod)
{
    used[nod]=1;
    for(auto it:v[nod])
    {
        int vec,cst;
        tie(vec,cst)=it;
        if(!used[vec])/// atentie - se pun doar muchii de la nodul proaspat adaugat spre noduri neadaugate
            pq.push(make_tuple(-cst,nod,vec));
        /// coada de prioritati scoate mereu ce e mai mare in top
        /// pentru a avea mereu costul minim ]n top pun costurile cu semn schimbat;
    }

}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    addEdges(1);
    int ramase=n-1;
    while(ramase)
    {
        int x,y,cst;
        tie(cst,x,y)=pq.top();
        pq.pop();
        if(!used[y])/// atentie cand pun in coada de prioritati mereu pun primul un nod din arbore ... eventual al doilea poate ca nu e
        {
            costAPM+=-cst;
            sol.push_back(make_pair(x,y));
            ramase--;
            addEdges(y);
        }
    }
    /// afisare  e la fel ca la kruskal
    g<<costAPM<<'\n';
    g<<n-1<<'\n';
    for(auto it:sol)
        g<<it.first<<' '<<it.second<<'\n';
    return 0;
}