#include<cstdio>
#include<algorithm>
#include<ctime>
#include<cstdlib>
using namespace std;
int dad[200001];
struct apm
{
    int x,y,cost,marcare;
};
apm v[200001];
bool sortare(apm a,apm b)
{
    if(a.cost==b.cost)
    {
        if(a.x==b.x)
        {
            return a.y<b.y;
        }
        return a.x<b.x;
    }
    return a.cost<b.cost;
}
int find(int nod)
{
    if(nod==dad[nod])
        return nod;
    else
        dad[nod]=find(dad[nod]);
}
void unionn(int nod1,int nod2)
{
    int a,b;
    a=find(nod1);
    b=find(nod2);
    if(a!=b)
    {
        if(rand()%2==0)
            dad[a]=b;
        else
            dad[b]=a;
    }
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,i,s,nrm;
    srand(time(0));
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].cost);
        v[i].marcare=0;
    }
    for(i=1;i<=n;i++)
        dad[i]=i;
    sort(v+1,v+m+1,sortare);
    nrm=0;
    s=0;
    for(i=1;i<=m&&nrm<n-1;i++)
    {
        if(find(v[i].x)!=find(v[i].y))
        {
            unionn(v[i].x,v[i].y);
            s=s+v[i].cost;
            nrm++;
            v[i].marcare=1;
        }
    }
    printf("%d\n%d\n",s,nrm);
    for(i=1;i<=m;i++)
        if(v[i].marcare==1)
            printf("%d %d\n",v[i].x,v[i].y);
    return 0;
}