#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct muchie
{
    int x,y,c;
}a[400001];
int n,m,i,t[200001],h[200001],k,cost,sol[200000];
int compare(muchie x,muchie y)
{
    return x.c<y.c;
}
int muchie (int x,int y)
{
    int r1,r2,x1,y1,c;
    r1=x;
    r2=y;
    while (r1!=t[r1]) r1=t[r1];
    while (r2!=t[r2]) r2=t[r2];
    if (r1==r2) return 0;
    while (t[x]!=r1) x1=t[x],t[x]=t[x1],x=x1;
    while (t[y]!=r2) y1=t[y],t[y]=t[y1],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;
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for (i=1;i<=m;i++)
        f>>a[i].x>>a[i].y>>a[i].c;
    sort (a+1,a+m+1,compare);
    for (i=1;i<=n;i++) t[i]=i,h[i]=1;
    k=0;
    i=1;
    while (k<n-1)
    {
        if (muchie(a[i].x,a[i].y)) cost+=a[i].c,sol[++k]=i;
        i++;
    }
    g<<cost<<'\n'<<n-1<<'\n';
    for (i=1;i<n;i++)
        g<<a[sol[i]].x<<" "<<a[sol[i]].y<<'\n';
    return 0;
}