#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;


int n,m,c[400001],conex,kawaii,dare;

struct muchii
{
    int x,y,cost;
    bool viz;
}p;

vector<muchii> T;
vector<muchii>::iterator it;


bool comp(muchii x1,muchii x2)
{
    return x1.cost<x2.cost;
}


void read()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d %d",&n,&m);
    int i;
    for(i=1;i<m+1;i++)
    {
        c[i]=i;

        scanf("%d %d %d",&p.x,&p.y,&p.cost);
        T.push_back(p);
    }
    conex=n;



}

void uf(int ltit,int rtit)
{
    int i;
    for(i=1;i<n+1;i++)
        if(c[i]==ltit) c[i]=rtit;
    conex--;dare++;
    kawaii+=it->cost;
    it->viz=true;
}

void krusky()
{
    for(it=T.begin();it!=T.end();it++)
    {

        if(conex==1) break;
        if(c[it->x]!=c[it->y])
            if(c[it->x]<c[it->y])
                uf(c[it->x],c[it->y]);
            else
                uf(c[it->y],c[it->x]);
    }
}


void afis()
{
    printf("%d",kawaii);printf("\n");
    printf("%d",dare);  printf("\n");

    for(it=T.begin();it!=T.end();it++)
        if(it->viz==true)
            {printf("%d %d", it->x, it->y);printf("\n");}
}

int main()
{
    read();
    sort(T.begin(),T.end(),comp);
    krusky();
    afis();

    return 0;
}