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

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

#define NMAX 200005

vector <pair<int, int> > graf[NMAX];

priority_queue<pair<int, pair< int, int> > > coada;
int n, m, viz[NMAX], tata[NMAX];

void citire(){

f>>n>>m;
for(int i = 0 ; i < m; i ++)
{
    int a,b,c;
    f>>a>>b>>c;
    graf[a].push_back({b,c});
    graf[b].push_back({a,c});
}
}
int ct;
void PRIM(int sursa){

int lungime = graf[sursa].size();
for(int i = 0; i < lungime; i ++)
{
    int vecin = graf[sursa][i].first;
    int cost = -graf[sursa][i].second;
    coada.push({cost,{sursa, vecin}});

}
tata[sursa] = 0;
viz[sursa] = 1;
ct = 0;
while(!coada.empty())
{
    pair<int,pair<int, int> > best = coada.top();
    coada.pop();

    int sursa = best.second.first;
    int vecin = best.second.second;
    int cost = best.first;

    if(!viz[vecin]){

        ct += -cost;
        viz[vecin] = 1;
        tata[vecin] = sursa;
        for(int i = 0; i < graf[vecin].size(); i ++)
        {

            coada.push({-graf[vecin][i].second, {vecin, graf[vecin][i].first}});
        }
    }
}

}
void afisare(int sursa){
    g<<ct<<'\n';
    g<<n-1<<'\n';
    for(int i = 1; i <= n; i ++)
    {
        if(i != sursa){

            g<<i<<" "<<tata[i]<<"\n";
        }
    }
}
int main()
{
    citire();
    PRIM(1);
    afisare(1);
    return 0;
}