#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;


int n,m,c[400001],conex,kawaii,dare;
int a[400010];

struct muchii
{
    int x,y,cost;
    bool viz;
}p;

vector<muchii> T;
vector<muchii>::iterator it;


bool comp(muchii x1,muchii x2)
{
    return x1.cost<x2.cost;
}

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

void read()
{

    f>>n>>m;
    int i;
    for(i=1;i<m+1;i++)
    {
        c[i]=i;
        f>>p.x;
        f>>p.y;
        f>>p.cost;
        T.push_back(p);
    }
    conex=n;



}

void uf(int ltit,int rtit)
{
    int i;
    for(i=1;i<n+1;i++)
        if(c[i]==ltit) c[i]=rtit;
    conex--;dare++;
    kawaii+=it->cost;
    it->viz=true;
}

void krusky()
{
    for(it=T.begin();it!=T.end();it++)
    {

        if(conex==1) break;
        if(c[it->x]!=c[it->y])
            if(c[it->x]<c[it->y])
                uf(c[it->x],c[it->y]);
            else
                uf(c[it->y],c[it->x]);
    }
}


void afis()
{
  //  for(it=T.begin();it!=T.end();it++)
  //      if(it->viz==true) kawaii+=it->cost;

    g<<kawaii<<"\n"<<dare<<"\n";

    for(it=T.begin();it!=T.end();it++)
        if(it->viz==true)
            g<<it->x<<' '<<it->y<<"\n";
}

int main()
{
    read();
    sort(T.begin(),T.end(),comp);
    krusky();
    afis();

    f.close();
    g.close();

    return 0;
}