#include <cstdio>
#include <algorithm>
using namespace std;

struct muchie
{
    int x,y,cost;
};

muchie u[400001],sel[400001];
int tata[200001],h[200001];
int n,m;

void citire()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
        scanf("%d%d%d",&u[i].x,&u[i].y,&u[i].cost);
}

bool cmp(muchie a,muchie b)
{
    return a.cost<b.cost;
}

void unifica(int x,int y)
{
    if(h[x]<h[y])
        tata[x]=y;
    else
        tata[y]=x;
    if(h[x]==h[y]) h[y]=h[y]+1;
}

int cauta(int x)
{
  int r=tata[x];
  while(tata[r]!=r)
    r=tata[r];
  int y=x;
  while(y!=r)
  {
      int t=tata[y];
      tata[y]=r;
      y=t;
  }
  return r;
}

void kruskal()
{
    int cstapm=0;
    sort(u,u+m,cmp);
    int k=0;
    int i=0;
    while(k<n-1)
    {
        if(cauta(u[i].x)!=cauta(u[i].y))
        {
            sel[k++]=u[i];
            cstapm+=u[i].cost;
            unifica(u[i].x,u[i].y);
        }
        i++;
    }
  printf("%d\n%d\n",cstapm,k);
  for(int i=0;i<k;i++)
    printf("%d %d\n",sel[i].x,sel[i].y);


}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    for(int i=1;i<=n;i++)
           h[i]=1,tata[i]=i;
    kruskal();
    return 0;
}