#include <fstream>
#include <algorithm>
#define Nmax 999999
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct Muchie
{
    int x,y,c;
}v[Nmax],w[Nmax];
int n,m,t[Nmax],h[Nmax],ct,i;

int muchie(int x,int y)
{
    int r1,r2,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;
        x=x1;
    }

    while(t[y]!=r2)
    {
        y1=t[y];
        t[y]=r2;
        y=y1;
    }

    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=0,i=1;
    while(k<n-1)
    {
        if(muchie(v[i].x,v[i].y))
        {
            ct+=v[i].c;
            w[k]=v[i];
            k++;

        }
        i++;
    }
}

int compare(Muchie x,Muchie y)
{
    if(x.c>y.c)return 0;
    return 1;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1,v+m+1,compare);
    ct=0;
    for(i=1;i<=n;i++)
    {
        t[i]=i;
        h[i]=1;
    }
    Kruskal();

    g<<ct<<'\n'<<n-1<<'\n';
    for(i=0;i<n-1;i++)
        g<<w[i].x<<" "<<w[i].y<<'\n';
    return 0;
}