#include <cstdio>
#include <algorithm>
#include <queue>
#define lim 200001
using namespace std;

struct muchie
{
    int x,y,cost;
}muchii[lim];
queue<int> Q;
int n,m;
void citire()
{
    scanf("%d %d",&n,&m);
    for(int i =0 ; i <m;i++)
    {
        scanf("%d %d %d",&muchii[i].x,&muchii[i].y,&muchii[i].cost);
    }
}

struct cmp
{
    bool operator()(muchie a, muchie b)const{

        return a.cost < b.cost;

    }
}mycmpObj;
int gr[lim];
int grupa(int x)
{
    if(gr[x] == x)
        return x;

    gr[x] = grupa(gr[x]);
    return gr[x];
}

int unirea(int x,int y)
{
    gr[grupa(x)] = grupa(y);
}


int cost;
void apm()
{
    for(int i=0;i<n;gr[i] = i,i++);

    for(int i =0 ; i < m; i++)
    {
        if(grupa(muchii[i].x) != grupa(muchii[i].y))
        {
            unirea(muchii[i].x,muchii[i].y);
            cost += muchii[i].cost;
            Q.push(i);
        }
    }
}

void afisare()
{
    printf("%d\n%d\n",cost,n-1);
    while(!Q.empty())
    {
        int x = Q.front();
        printf("%d %d\n",muchii[x].x,muchii[x].y);
        Q.pop();
    }

}


int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    sort(muchii,muchii+m,mycmpObj);
    apm();
    afisare();
    return 0;
}