#include <fstream>
#define N 200002
#include <algorithm>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct bla
{
    int x,y,co;
}v[N];

bool cmp (bla A, bla B)
{
    return (A.co<B.co);
}
int tata[N], rang[N];
struct
{
    int a,b;
}sol[N];

int root(int x)
{
    while(x!=tata[x]) x=tata[x];
    return x;
}
void unite(int x, int y)
{
    if(rang[x]<rang[y])
        tata[x]=y;
    else
        tata[y]=x;
    if(rang[x]==rang[y])
        ++rang[x];
}
int main()
{
    int n,m,rx,ry,ss=0,nr=0;
    f>>n>>m;
    for(int i=1;i<=n;++i) tata[i]=i;
    for(int i=1;i<=m;++i)
        f>>v[i].x>>v[i].y>>v[i].co;
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=m;++i)
    {
        rx=root(v[i].x);
        ry=root(v[i].y);
        if(rx!=ry)
            unite(rx,ry),ss=ss+v[i].co,sol[++nr]={v[i].x,v[i].y};
    }
    g<<ss<<'\n'<<nr<<'\n';
    for(int i=1;i<=nr;++i)
        g<<sol[i].a<<' '<<sol[i].b<<'\n';
    f.close();
    g.close();
    return 0;
}