#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 400001
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

int n,m,i,nr=0;
int costminim=0;
long long tata[NMAX/2];
struct muchie
{
    int x,y,c;
}v1[NMAX],v2[NMAX];

bool comparare(muchie a, muchie b)
{
    if(a.c<b.c) return true;
    return false;
}

int radacinaa(int x)
{
    int R=x;
    while(R!=tata[R]) R=tata[R];
    while(x!=R)
    {
        int aux=tata[x];
        tata[x]=R;
        x=aux;
    }
    return R;
}


int main()
{
    in>>n>>m;
    for(i=1;i<=n;i++) tata[i]=i;
    for(i=1;i<=m;i++)
    {
        in>>v1[i].x>>v1[i].y>>v1[i].c;
    }
    sort(v1+1,v1+m+1,comparare);
    for(i=1;i<=m;i++)
    {
        if(radacinaa(v1[i].x)!=radacinaa(v1[i].y))
        {
            tata[radacinaa(v1[i].x)]=radacinaa(v1[i].y);
            costminim+=v1[i].c;
            nr++;
            v2[nr].x=v1[i].x;
            v2[nr].y=v1[i].y;
        }
    }
    if(nr!=0) printf("ALgoritmul a decurs cu succes");
    out<<costminim<<'\n'<<nr<<'\n';
    for(i=1;i<=nr;i++)
    {
        out<<v2[i].x<<" "<<v2[i].y<<'\n';
    }
    in.close();
    out.close();
    return 0;
}