#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++) t[i]=i;
}

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

int FIND(int u)
{
    if(t[u]==u) return u;
    else return t[u]=FIND(t[u]);
}

void UNION(int x,int y)
{
    int a=FIND(x);
    int b=FIND(y);
    if(h[a]>h[b])
        {
            t[b]=a;
            h[a]+=h[b];
        }
    else
      {
          t[a]=b;
          h[b]+=h[a];
      }
}
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;
}