#include <fstream>
#include <vector>
#include <queue>
#define MAXN 200005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct muchie{
    long nod,cost;};

struct muchie2{
    long nod1,nod2,cost;};

struct Comp{
    bool operator()(muchie2 a,muchie2 b){
    return a.cost>b.cost;}};

long n,m,x,y,c,sol[2][MAXN],cnt,cost_total;
bool uz[MAXN];
vector<muchie> G[MAXN];
muchie aux;
priority_queue<muchie2,vector<muchie2>,Comp> h;
muchie2 aux2,t;


int main()
{
    long i;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>c;
        aux.cost=c;
        aux.nod=y;
        G[x].push_back(aux);
        aux.nod=x;
        G[y].push_back(aux);}
    uz[1]=1;
    cnt++;
    aux2.nod1=1;
    for(i=0;i<G[1].size();i++){
        aux2.nod2=G[1][i].nod;
        aux2.cost=G[1][i].cost;
        h.push(aux2);}
    while(cnt<n){
        t=h.top();
        h.pop();
        while(uz[t.nod2]){
            t=h.top();
            h.pop();}
        cost_total+=t.cost;
        sol[0][cnt]=t.nod1;
        sol[1][cnt++]=t.nod2;
        uz[t.nod2]=1;
        x=t.nod2;
        aux2.nod1=x;
        for(i=0;i<G[x].size();i++){
            if(!uz[G[x][i].nod]){
                aux2.nod2=G[x][i].nod;
                aux2.cost=G[x][i].cost;
                h.push(aux2);}}}
    g<<cost_total<<'\n'<<n-1<<'\n';
    for(i=1;i<n;i++)
        g<<sol[0][i]<<' '<<sol[1][i]<<'\n';
    f.close();
    g.close();
    return 0;
}