#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#define inf 0x7fffffff
using namespace std;

class mycomparison
{
  bool reverse;
public:
  mycomparison(const bool& revparam=false)
    {reverse=revparam;}
  bool operator() (const pair<int,int>& lhs, const pair<int,int>&rhs) const
  {
    return lhs.second>rhs.second;
  }
};

int sol;
int n,m1;
vector< pair<int,int> > m[200010];
vector<int> sola,solb;
vector<int> arb;
priority_queue< pair<int,int> , vector< pair<int,int> > , mycomparison > q;
int val[200010],p[200010];
bitset<200010> viz;


int main()
{
    int a,b,c;
    int i,j;
    ifstream t1("apm.in");
    ofstream t2("apm.out");

    t1>>n>>m1;
    for(i=1;i<=m1;i++)
    {
        t1>>a>>b>>c;
        m[a].push_back( make_pair(b,c));
        m[b].push_back( make_pair(a,c));
    }

    for(i=1;i<=n;i++) val[i]=inf;
    arb.push_back(1);
    val[1]=-1001;
    int nod,cont=0;


    while(cont<n-1)
    {
        nod=arb[cont];
        //cout<<nod<<'\n';
        viz[nod]=1;
        for(i=0;i<m[nod].size();i++)
        {
          //  cout<<m[nod][i].first<<' ';
            if( m[nod][i].second< val[ m[nod][i].first] && !viz[m[nod][i].first])
            {
                val[ m[nod][i].first]=m[nod][i].second;
                p[m[nod][i].first]=nod;
                q.push( m[nod][i] );
            }
        }
        //cout<<'\n';

        //for(i=1;i<=n;i++) cout<<val[i]<<' '; cout<<'\n';
        //cout<<q.top().first<<' '<<q.top().second<<'\n';

        while( viz[ q.top().first ])
            q.pop();

        arb.push_back( q.top().first);
        cont++;
        sol+=q.top().second;
        sola.push_back( p[ q.top().first]);
        solb.push_back( q.top().first);
        //cout<<cont<<"\n\n";
    }

    t2<<sol<<'\n';
    t2<<n-1<<'\n';
    for(i=0;i<sola.size();i++)
        t2<<sola[i]<<' '<<solb[i]<<'\n';

    return 0;
}