#include<bits/stdc++.h>
using namespace std;
ifstream f("kruskal.in");
ofstream g("kruskal.out");

vector<int> p;
vector<int> sz;

int find_parent(int nod) //reprezentantul lui nod
{
    if(p[nod]==nod)
        return nod;
    return p[nod]=find_parent(p[nod]);
}

int unite(int x, int y)
{
    x=find_parent(x);
     y=find_parent(y);
     if(x==y)
     {
         return 0;
     }
     if(sz[x]>sz[y])
     {
         swap(x,y);
     }
     p[x]=y;
     sz[y]+=sz[x];
}

struct muchie{
int x;int y;int cost;
};
bool crit(muchie a,muchie b)
{
    if(a.cost!=b.cost)
  return a.cost<b.cost;
  if(a.x!=b.x)
  return a.x<b.x;
  if(a.y!=b.y)
  return a.y<b.y;
}
int main()
{
   int n,m,i,total=0;
   f>>n>>m;
    p.resize(200001);
    sz.resize(200001);
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
        sz[i]=1;
    }
  vector<tuple<int,int,int>>edg(m);

  for(auto& [cost,u,v]:edg)
  {
      f>>u>>v>>cost;
  }
  sort(edg.begin(),edg.end());
  vector<pair<int,int>>rep;
  for(auto[cost,u,v] :edg)
  {
      if(find_parent(u)!=find_parent(v))
      {
          rep.push_back({u,v});
          total+=cost;
          unite(u,v);

      }
  }
  g<<total<<endl;
  g<<n-1<<endl;
  for(auto [u,v] : rep)
  {
      g<<u<<" "<<v<<endl;
  }
f.close();
g.close();
    return 0;
}