#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
const int NMAX=200000,MMAX=400000;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie
{
    int i,j,c;
};

muchie M[MMAX+1];

int n, m, cost;
int cc[NMAX+1], nrm[NMAX+1], nm;

void citire()
{
    fin>>n>>m;
    for(int k=1; k<=m; k++)
        fin>>M[k].i>>M[k].j>>M[k].c;
}

void afis()
{
    fout<<cost<<'\n'<<nm<<'\n';
    for(int i=1; i<=nm; i++)
    {
        int k=nrm[i];
        fout<<M[k].i<<' '<<M[k].j<<'\n';
    }
}

bool comp(const muchie &a, const muchie &b)
{
    return a.c<b.c;
}

int Find(int i)
{
    if(cc[i]==0) return i;
    return cc[i]=Find(cc[i]);
}

void kruskal()
{
    sort(M+1,M+m+1,comp);
    for(int i=1; i<=m; i++)
    {
        int ci=Find(M[i].i),
            cj=Find(M[i].j);
        if(ci!=cj)
        {
            cost+=M[i].c;
            cc[ci]=cj;
            nrm[++nm]=i;
            if(nm==n-1) break;
        }
    }
}

int main()
{
    citire();
    kruskal();
    afis();

    fin.close();
    fout.close();
    return 0;
}