#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int N=200001,inf=1000000001;
vector <int> a[N],c[N];
int n,m,d[N],poz[N],h[N],nh,ct,pred[N];
bool viz[N];
void schimba(int p,int q)
{
    int aux=h[p];
    h[p]=h[q];
    h[q]=aux;
    poz[h[p]]=p;
    poz[h[q]]=q;
}

void urca(int p)
{
    while(p>1 && d[h[p]]<d[h[p/2]]){
        schimba(p,p/2);
        p/=2;
    }
}

void coboara(int p)
{
    int fs=2*p,fd=2*p+1,bun=p;
    if(fs<=nh && d[h[fs]]<d[h[bun]])
        bun=fs;
    if(fd<=nh && d[h[fd]]<d[h[bun]])
        bun=fd;
    if(bun!=p){
        schimba(bun,p);
        coboara(bun);
    }
}

void sterge(int p)
{
    schimba(p,nh);
    nh--;
    urca(p);
    coboara(p);
}

void scrie()
{
    for (int i = 1; i <= nh; i++)
    {
        g << "(" << h[i] << "," << d[h[i]] << ") ";
    }
    g << "\n";
}

void apm(int x0)
{
    nh=n;
    for(int i=1;i<=n;i++){
        d[i]=inf;
        h[i]=i;
        poz[i]=i;
    }
    d[x0]=0;
    urca(poz[x0]);
    while(nh>0 && d[h[1]]!=inf){
        //scrie();
        int x=h[1];
        sterge(1);
        viz[x]=true;
        for(int i=0;i<a[x].size();i++){
            int y=a[x][i];
            int cost=c[x][i];
            if(viz[y])
               continue;
            if(cost<d[y]){
               d[y]=cost;
               pred[y]=x;
               urca(poz[y]);
            }
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,cost;
        f>>x>>y>>cost;
        a[x].push_back(y);
        a[y].push_back(x);
        c[x].push_back(cost);
        c[y].push_back(cost);
    }
    apm(1);
    for(int i=2;i<=n;i++)
        ct+=d[i];
    g<<ct<<'\n'<<n-1<<'\n';
    for(int i=2;i<=n;i++)
        g<<pred[i]<<' '<<i<<'\n';
    return 0;
}