#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

#define nmax 200005
using namespace std;

struct muchie
{
    pair<int,int> v;
    int cost;
};
int n,m;
int p[nmax];
muchie s[nmax*2];
vector< pair<int,int> > v;
struct cmp
{
    bool operator()(muchie A,muchie B)
    {
        return A.cost<B.cost;
    }
};
void read()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d %d %d",&s[i].v.first,&s[i].v.second,&s[i].cost);
    sort(s+1,s+m+1,cmp());
    for(int i=1;i<=n;i++)
        p[i]=i;
}

int parinte(int initial)
{
    int curent = initial;
    while(curent != p[curent] )
    {
        curent=p[curent];
        p[initial]= curent;
    }
    return curent;
}

int conectat(muchie A)
{
    if(parinte(A.v.first)!= parinte(A.v.second))
        return 0;
    return 1;
}
void kruskal()
{
    int tcost=0;
    int nmuchii=0;
    for(int i=1;i<=m;i++)
    {
        if(!conectat(s[i]))
        {
            p[parinte(s[i].v.first)]=parinte(s[i].v.second);
            v.push_back(s[i].v);
            tcost+=s[i].cost;
            nmuchii++;
        }
        if(nmuchii==n-1)
         break;
    }
    printf("%d\n",tcost);
    printf("%d\n",nmuchii);
    for(int i=0;i<nmuchii;i++)
        printf("%d %d\n",v[i].first,v[i].second);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    read();
    kruskal();
    return 0;
}