#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,cost,nrsel,con[200002],sol[400002],i,j;
struct muchii
{
    int x,y,z;
}a[400002];
int cmp(muchii p,muchii q)
{
    return p.z <q.z;
}
void citire()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    }
}
int comp(int i)
{
    if(con[i]==i) return i;
    con[i]=comp(con[i]);
    return con[i];
}
void kruskal()
{
    for(i=1;i<=n;i++) con[i]=i;
    sort(a+1,a+m+1,cmp);
    i=1;
    while(nrsel<n-1)
    {
        if(comp(a[i].x)!=comp(a[i].y))
        {
            sol[i]=1;
            nrsel++;
            cost+=a[i].z;
            con[comp(a[i].x)]=comp(con[a[i].y]);

        }
        i++;
    }
}
void afisare()
{
    printf("%d\n%d\n",cost,n-1);
    for(i=1;i<=m;i++) if(sol[i]==1) printf("%d %d\n",a[i].x,a[i].y);

}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    kruskal();
    afisare();
    return 0;
}