#include <iostream>
#include<vector>
#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 200001;
const int MMAX = 400001;

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

struct muchie
{
    int x,y,cost;
};
int COST;
int cmp(muchie x,muchie y)
{
    return (x.cost<y.cost);
}
int get_root(int x, vector<int>& comp)
{
//    if(comp[x]!=x)
//    {
//        x=comp[x];
//        return get_root(x, comp);
//    }
//    return x;
  int r = x;
  while(r!=comp[r]) r= comp[r];
  while(x!=comp[x])
  {
      int tmp = comp[x];
      comp[x]=r;
      x = tmp;
  }
  return r;
}
bool disjoint(int x, int y, vector<int>& comp)
{
    return get_root(x, comp) != get_root(y, comp);
}
void uneste(int x, int y,vector<int>&rang,vector<int> &comp)
{
    int par_x=get_root(x,comp);
    int par_y= get_root(y,comp);
    if(rang[par_x]<rang[par_y])
        comp[par_x]=comp[par_y];
    else if(rang[par_x]>rang[par_y])
        comp[par_y]=comp[par_x];
    else {
        comp[par_x] = comp[par_y];
        rang[par_y]++;
    }

}
int main() {
    int N,M,x,y,c;
    fin>>N>>M;
    vector<muchie> muchii;
    vector<muchie> sol;
    vector<int> comp(N);
    vector<int> rang(N,0);
    for(int i=0;i<comp.size();i++)
          comp[i]=i;
    for(int i=0;i<M;i++)
    {
        fin>>x>>y>>c;
        muchii.push_back({x-1,y-1,c});
    }
//    for(int i=0;i<muchii.size();i++)
//        cout<<muchii[i].x<<" "<<muchii[i].y<<" "<<muchii[i].cost<<endl;
    sort(muchii.begin(),muchii.end(),cmp);
    int cnt=0,i=0;
    while(cnt<N-1)
    {
        muchie temp = muchii[i];
        if(disjoint(temp.x,temp.y,comp))
        {
            COST+=temp.cost;
            uneste(temp.x,temp.y,rang,comp);
            sol.push_back({temp.x+1,temp.y+1,temp.cost});
            cnt++;
        }
        i++;
    }
    fout<<COST<<'\n'<<sol.size()<<'\n';
    for(int i=0;i<sol.size();i++)
        fout<<sol[i].x<<" "<<sol[i].y<<'\n';

    return 0;
}