#include <fstream>
#include <algorithm>
#define nmax 400001
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;

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

muchie v[nmax];
int t[nmax],r[nmax*2],h[nmax];

void read()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
       {
           fin>>v[i].x>>v[i].y>>v[i].cost;
       }
    for(int i=1; i<=n; i++) h[i]=1;
}

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

int FIND(int x)
{
    while(t[x]!=0) x=t[x];
    return x;
}

void UNION(int x,int y)
{
    if(h[x]>h[y])
         t[x]=y;
    else
      {
          t[x]=y;
          if(h[x]==h[y]) h[y]++;
      }
}
struct m_arb
{
    int x,y;
};
m_arb v2[nmax];

int main()
{
    read();
    sort(v+1,v+m+1,cmp);
    int nr=0;
    int i=1;
    int ct=0;
    int s=0;
    while(nr<n-1)
        {
            int x=v[i].x;
            int y=v[i].y;
            int t_x=FIND(x);
            int t_y=FIND(y);
            if(t_x!=t_y)
               {
                   nr++;
                   ct++;
                   v2[ct].x=x;
                   v2[ct].y=y;
                   UNION(x,y);
                   s+=v[i].cost;
               }
            i++;
        }
   fout<<s<<"\n";
   fout<<ct<<"\n";
   for(i=1; i<=ct; i++)
        fout<<v2[i].x<<" "<<v2[i].y<<"\n";
    return 0;
}