#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int tata[1500000],h[1500000],n,m,i,suma;
void initializare(int u)
{
    tata[u]=h[u]=0;
}
struct muchie
{
    int x,y,cost;
};
muchie vec[15000000],w[1500000];
bool compara(muchie u,muchie v)
{
    if(u.cost>v.cost)
        return false;
    return true;
}
int componenta(int u)
{
    if (tata[u]==0)
    return u;
    tata[u]=componenta(tata[u]);
return tata[u];
}

void reuneste(int u,int v)
{
    int ru,rv;
    ru=componenta(u);
    rv=componenta(v);
    if(h[ru]>h[rv])
        tata[rv]=ru;
    else
    {
        tata[ru]=rv;
        if(h[ru]==h[rv])
            h[rv]=h[rv]+1;
    }
}
int main()
{
    int u,v,ok=0;
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>vec[i].x>>vec[i].y>>vec[i].cost;
    sort(vec+1,vec+m+1,compara);
    for(i=1;i<=m;i++)
    {
      u=vec[i].x;
      v=vec[i].y;
      if(componenta(u)!=componenta(v))
      {
          reuneste(u,v);
          suma+=vec[i].cost;
          ok++;
          w[ok].x=u;
          w[ok].y=v;
          if(ok==n-1)
            break;
      }
     }
     g<<suma<<'\n'<<ok<<'\n';
     for(i=1;i<=n-1;i++)
        g<<w[i].x<<" "<<w[i].y<<'\n';
return 0;
}