#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
int ct,t[200010],sol[200010],h[200010],n,m;
struct Muchie
{
    int X,Y,c;
} u[200010];
int compare (Muchie a, Muchie b)
{
    return a.c<b.c;
}
int muchie(int x, int y)
{
    int r1,r2,k,C,x1,y1;
    r1=x;
    r2=y;
    while(t[r1]!=r1) r1=t[r1];
    while(t[r2]!=r2) r2=t[r2];

    if(r1==r2) return 0;
    while(t[x]!=r1)
    {
        x1=t[x];
        t[x]=r1;
    }
    while(t[y]!=r2)
    {
        y1=t[y];
        t[y]=r2;
    }
    if(h[r1]>h[r2])
    {
        t[r2]=r1;
        C=r1;
    }
    else
    {
        t[r1]=r2;
        C=r2;
    }
    if(h[r1]==h[r2]) h[C]++;
    return 1;
}
void kruskal ()
{
    int k,i;
    k=0;
    i=1;
    while(k<n-1)
    {
        if(muchie(u[i].X,u[i].Y))
        {
            ct+=u[i].c;
            sol[++k]=i;
        }
        i++;
    }
}
int main()
{
    int i;
    f>>n>>m;
    for(i=1; i<=n; i++)
    {
        h[i]=1;
        t[i]=i;
    }
    for(i=1; i<=m; i++)
    {
        f>>u[i].X>>u[i].Y>>u[i].c;
    }
    sort(u+1,u+m+1,compare);
    kruskal();
    g<<ct<<'\n'<<n-1<<'\n';
    for(i=1; i<=n-1; i++)
    {
        g<<u[sol[i]].Y<<" "<<u[sol[i]].X<<'\n';
    }
    return 0;
}