#include <fstream>
#include <vector>
#include <queue>

#define MAXN 200000

using namespace std;

ifstream fin( "apm.in" );
ofstream fout( "apm.out" );

struct Edge
{
  int x, y, w;
};

class cmp
{
  public:
    bool operator() ( Edge a, Edge b )
    {
      return a.w>b.w;
    }
};

vector<Edge> v[MAXN+5];
priority_queue<Edge,vector<Edge>,cmp> q;

bool f[MAXN+5];
Edge sol[MAXN+5];

inline void add( int k )
{
  for( vector<Edge>::iterator it=v[k].begin();it!=v[k].end();it++ )
      if( !f[it->y] )
        q.push(*it);
}

int main()
{
  int n, m;

  fin>>n>>m;

  for( int i=1;i<=m;i++ )
  {
    int a, b, c;

    fin>>a>>b>>c;

    v[a].push_back(Edge{a,b,c});
    v[b].push_back(Edge{b,a,c});
  }

  int cost=0;

  f[1]=true;

  add(1);

  for( int i=1;i<n;i++ )
  {
    Edge t=q.top();
    q.pop();


    if( !f[t.y] )
    {
      f[t.y]=true;

      add(t.y);

      sol[i]=t;

      cost+=t.w;
    }
    else
      i--;
  }

  fout<<cost<<'\n'<<n-1<<'\n';

  for( int i=1;i<n;i++ )
    fout<<sol[i].x<<" "<<sol[i].y<<'\n';

  return 0;
}