#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 mark;
};
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)
{
    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);
        }
        M[i].mark=1;
        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];
    for(i=0;i<m;i++) {f>>M[i].x>>M[i].y>>M[i].c; M[i].mark=0;}
    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)<<'\n'<<n-1<<'\n';
    for(i=0;i<m;i++) if(M[i].mark==1) g<<M[i].x<<' '<<M[i].y<<'\n';
}