#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int t[100001],v2[100001];
int query(int x)
{
    int r=x;
    while(r!=t[r]) r=t[r];
    while(x!=r)
    {
        int aux=t[x];
        t[x]=r;
        x=aux;
    }
    return r;
}
struct nod
{
    int x,y,c;
}v[1000];
bool inline cmp(nod a,nod b)
{
    return(a.c<b.c);
}
int main()
{
    int i,n,m,cost=0,p=1;
    in>>n>>m;
    for(i=1;i<=n;i++)
        t[i]=i;
    for(i=1;i<=m;i++)
        in>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        if(query(v[i].x)!=query(v[i].y))
        {
            t[query(v[i].x)]=query(v[i].y);
            cost=cost+v[i].c;
            v2[p]=v[i].x;
            v2[++p]=v[i].y;
            p++;
        }
    }
    out<<cost<<'\n'<<(p-1)/2<<'\n';
    for(i=1;i<p;i+=2)
       out<<v2[i+1]<<" "<<v2[i]<<'\n';
}