#include <iostream>
#include <fstream>
#define inf 1e9

using namespace std;

ifstream in ("apm.in");
ofstream out ("apm.out");

const int N=200001;
const int M=400001;
int h[N],d[N],poz[N],cost[N],vf[M],lst[N],urm[M],nh,nr,ct,pred[N],n;
bool selectat[N];

adauga_muchie (int x, int y, int c)
{
    vf[++nr]=y;
    cost[nr]=c;
    urm[nr]=lst[x];
    lst[x]=nr;
}
void schimb (int a, int b)
{
    swap (h[a],h[b]);
    poz[h[a]]=a;
    poz[h[b]]=b;
}
void urca (int x)
{
    while (x>1 && d[h[x]]<d[h[x/2]])
    {
        schimb (x,x/2);
        x/=2;
    }
}
void coboara (int x)
{
    int fs=x*2,fd=x*2+1,bun=x;
    if (fs<=nh && d[h[fs]]<d[h[bun]])
        bun=fs;
    if (fd<=nh && d[h[fd]]<d[h[bun]])
        bun=fd;
    if (bun!=x)
    {
        schimb (bun,x);
        coboara (bun);
    }
}
void adauga (int x)
{
    h[++nh]=x;
    poz[x]=nh;
    urca(nh);
}
void sterge (int x)
{
    schimb (x,nh--);
    coboara (x);
    urca (x);
}
void prim ()
{
    for (int i=2;i<=n;i++)
    {
        d[i]=inf;
        adauga (i);
    }
    d[1]=0;
    adauga (1);
    while (nh>0)
    {
        int x=h[1];
        sterge (1);
        ct+=d[x];
        selectat[x]=true;
        for (int p=lst[x];p!=0;p=urm[p])
        {
            int y=vf[p];
            int c=cost[p];
            if (c<d[y] && !selectat[y])
            {
                d[y]=c;
                urca (poz[y]);
                pred[y]=x;
            }
        }
    }
}
int main()
{
    int m,x,y,c;
    in>>n>>m;
    for (int i=1;i<=m;i++)
    {
        in>>x>>y>>c;
        adauga_muchie (x,y,c);
        adauga_muchie (y,x,c);
    }
    prim ();
    out<<ct<<'\n'<<n-1<<'\n';
    for (int i=2;i<=n;i++)
    {
        out<<i<<' '<<pred[i]<<'\n';
    }
    return 0;
}