#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie
{
    int x,y;
};
struct nod
{
    int c;
    muchie m;
};
struct compar
{
  bool operator()(nod x, nod y)
{
    return x.c>y.c;
}
};


priority_queue <nod, vector <nod>, compar> Q;
vector <muchie> Sol;
int n,m,cost=0;
int dad[200001];

void citire()
{
   int x,y,c;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
   {    fin>>x>>y>>c;
        nod a;
        a.m.x=x;
        a.m.y=y;
        a.c=c;
        Q.push(a);
    }

}
void afish()
{
    fout<<cost<<"\n"<<n-1<<"\n";
    for(auto&v:Sol)
    {
        fout<<v.x<<" "<<v.y<<"\n";
    }
}
void init()
{
    for(int i=1;i<=n;i++)dad[i]=i;///fiecare are radacina lui
}
int daddy(int x)
{
    if(dad[x]==x) return x;///e radacina
    else return daddy(dad[x]);///caut rdacina tatalui
}
void Prim()
{   int x,y,i=1,dx,dy;
    while(i<=n-1)///cat timp arborele este incoplet
    {
        x=Q.top().m.x;
        y=Q.top().m.y;
        dx=daddy(x);
        dy=daddy(y);
        if(dx!=dy)
        {
            i++;///am gasit o muchie buna
            dad[max(dx,dy)]=min(dx,dy);///tatal lui x il primeste pe y
            cost+=Q.top().c;
            Sol.push_back(Q.top().m);
        }
        Q.pop();
    }
}


int main()
{
    citire();
    init();
    Prim();
    afish();
    return 0;
}