#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
typedef struct
{
    int x,y,cost;
}NOD;
std::vector< NOD > a;
std::vector< std::pair<int,int> > muchii;
std::vector<int> tata,h;
int n,m,x,y,cost;
bool CMP(const NOD A,const NOD B)
{
    return A.cost<B.cost;
}
typedef struct
{
    bool operator()(const NOD A,int B)
    {
        return A.cost>B;
    }
    bool operator()(int A,const NOD B)
    {
        return A<B.cost;
    }
}Compare;

void Union(int x0,int y0)
{
    if( h[x0]>h[y0] )tata[y0] = x0;
    else if( h[x0]<h[y0] )tata[x0] = y0;
    else
    {
        tata[y0] = x0;
        ++h[x0];
    }
}

int FindRad(int x0)
{
    int rad = x0,aux = 0;
    while(tata[rad])rad = tata[rad];
    while(tata[x0])
    {
        aux = tata[x0];
        tata[x0] = rad;
        x0 = aux;
    }
    return rad;
}

void kruskal()
{
    int contor = 0;
    cost = 0;
    int Rada,Radb;
    for(int i=0;contor<n-1;++i)
    {
        Rada = FindRad(a[i].x);
        Radb = FindRad(a[i].y);
        if(Rada!=Radb)
        {
            ++contor;
            cost = cost + a[i].cost;
            Union(Rada,Radb);
            muchii.push_back( std::make_pair(a[i].x,a[i].y) );
        }
    }
    printf("%d\n%d\n",cost,n-1);
    for(int i=0;i<muchii.size();++i)
    {
        printf("%d %d\n",muchii[i].first,muchii[i].second);
    }
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    tata.resize(n+1);
    h.resize(n+1);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d %d",&x,&y,&cost);
        NOD aux;
        aux.x = x;
        aux.y = y;
        aux.cost = cost;
        std::vector< NOD >::iterator it;
        it = upper_bound(a.begin(),a.end(),cost,Compare());
        a.insert(it,aux);
    }
    //sort(a.begin(),a.end(),CMP);
    kruskal();
    return 0;
}