#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    int x,y;
    int c;
};
bool cmp(muchie a, muchie b)
{
    return a.c<b.c;
}
int findar(int x, int*&t)
{
    if(t[x]==0) return x;
    else findar(t[x],t);
}
void unire(int x, int y, int*&t, int*&h)
{
    if(h[x]>h[y]) t[y]=x;
    else if(h[x]<h[y]) t[x]=y;
         else {t[y]=x; h[x]++;}
}
int kruskal(int n, int m, muchie*&M, int*&t, int*&h, muchie*&P)
{
    int s=0,k,i=0,a,b;
    for(k=0;k<n-1;k++)
    {
        a=findar(M[i].x,t);
        b=findar(M[i].y,t);
        while(a==b && i<=m)
        {
            i++;
            a=findar(M[i].x,t);
            b=findar(M[i].y,t);
        }
        P[i]=M[i];
        s=s+M[i].c;
        unire(a,b,t,h);
    }
    return s;
}
int main()
{
    int n,m,i;
    f>>n>>m;
    muchie *M=new muchie [m],*P=new muchie[n-1];
    for(i=0;i<m;i++) f>>M[i].x>>M[i].y>>M[i].c;
    sort(M,M+m,cmp);
    int *t=new int [n+1], *h=new int [n+1];
    for(i=1;i<=n;i++) {t[i]=0; h[i]=0;}
    g<<kruskal(n,m,M,t,h,P)<<'\n'<<n-1<<'\n';
    for(i=0;i<n-1;i++) g<<P[i].x<<' '<<P[i].y<<'\n';
}