/*
Descrirea soluției
Se pleacă de la un subgraf/arbore format dintr-un singur vârf, la alegere. La fiecare pas se selectează un nou vârf neselectat încă și adiacent cu unul din vârfurile deja selectate în APM, astfel încât muchia corespunzătoare să fie de cost minim.
Vârful nou adăugat este terminal deci nu se vor forma cicluri, iar subgraful selectat construit este conex, deci este arbore. Dacă se începe construirea din alt vârf  este posibil sa se obțină alt APM, dar costul va fi acelasi (APM-ul nu este neaparat unic).
Algoritmul se execută în n-1 pași, la fiecare pas fiind selectat un vârf din graf aflat la distanță minimă de vârfurile deja selectate. Această operație se execută în O(logN), folosind un MinHeap pentru memorarea muchiilor din arbore cu costurile lor,
în vârful heap-ului aflându-se muchia de cost minim. Deci, algoritmul are complexitatea O(N logN)
*/

#include <fstream>
#include <vector>
#include <queue>
#define nmax 200005
#define inf 2e9
#define PII pair<int,int>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

priority_queue<pair<int, PII>, vector<pair<int,PII> >, greater<pair<int,PII> > >h;
vector<PII> v[nmax];
int n,m,viz[nmax];

struct apm
{
    int x,y;
} sol[nmax];

int prim(int nod)
{
    int i, j, vecin, cost, ct=0;

    viz[nod]=1;

    for(i=1; i<n; i++)
    {
        for(j=0; j<v[nod].size(); j++)
        {
            vecin = v[nod][j].second;
            cost = v[nod][j].first;
            if(!viz[vecin]) h.push({cost,{nod,vecin}});
        }

        PII muchie = h.top().second;

        while(viz[muchie.second]) h.pop();

        ct += h.top().first;
        viz[muchie.second] = 1;
        sol[i].x = muchie.first;
        sol[i].y = muchie.second;
        nod = muchie.second;
        h.pop();
    }
    return ct;
}

int main()
{
    int a,b,c,i;

    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>a>>b>>c;
        v[a].push_back({c, b});
        v[b].push_back({c, a});
    }

    g<<prim(1)<<'\n'<<n-1<<'\n';
    for(i=1; i<n; i++)
    {
        g<<sol[i].x<<" "<<sol[i].y<<'\n';
    }
    return 0;
}