#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int N,M,cost,parent[200100];
vector <int> rez;

struct muchie
{
    int f;
    int l;
    int c;
} m[400100];

int comp(muchie a, muchie b)
{
    return a.c<b.c;
}


int root(int k)
{
    int ret=k;
    while(parent[ret])
    {
        ret=parent[ret];
    }
    return ret;
}

void compress(int k)
{
    int temp=k;
    int r=root(k);
    while(parent[temp])
    {
        int temp1=parent[temp];
        parent[temp]=r;
        temp=temp1;
    }
}

bool arbore(int k)
{
    int d=root(m[k].f);
    int e=root(m[k].l);

    if(d==e)
    {
        compress(m[k].f);
        compress(m[k].l);
        return 0;
    }

    else
    {
        parent[d]=e;
        return 1;
    }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&N,&M);

    for(int i=1;i<=M;++i)
    {
        scanf("%d%d%d",&m[i].f,&m[i].l,&m[i].c);
    }
    sort(m+1,m+M+1,comp);

    for(int i=1;i<=M;++i)
    {
        if( arbore(i) )
        {
            cost=cost+m[i].c;
            rez.push_back(i);
        }
    }

    int x=rez.size();
    printf("%d\n%d\n",cost,x);

    for(int i=0;i<x;++i)
        printf("%d %d\n",m[rez[i]].f,m[rez[i]].l);


    return 0;
}