#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define Mmax 400010
using namespace std;

struct muchie
{
    int x,y,c;
}U[Mmax];

vector <int> Sol;
int I[Mmax],Rad[Mmax];
int N,M;
int Costmin;

int cmp(muchie A, muchie B)
{
    return A.c<B.c;
}

int Radacina(int x)
{
    if(Rad[x]==x)
        return x;
    Rad[x]=Radacina(Rad[x]);
    return Rad[x];
}

void Citire_si_formare()
{
    scanf("%d %d",&N,&M);
    for(int i=1;i<=M;++i)
    {
        scanf("%d %d %d",&U[i].x,&U[i].y,&U[i].c);
        I[i]=i;
    }
    for(int i=1;i<=N;++i)
        Rad[i]=i;
}


void Kruskal()
{
    for(int i=1;i<=M;++i)
    {
        if(Radacina(U[i].x)!=Radacina(U[i].y))
        {
            Costmin+=U[i].c;
            Rad[Radacina(U[i].x)]=Radacina(U[i].y);
            Sol.push_back(i);
        }
    }
}

void Afisare()
{
    printf("%d\n%d\n",Costmin,Sol.size());
    for(int i=0;i<Sol.size();++i)
        printf("%d %d\n",U[Sol[i]].x,U[Sol[i]].y);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    Citire_si_formare();
    sort(U+1,U+M+1,cmp);
    Kruskal();
    Afisare();
    return 0;
}