#include <fstream>
#include <queue>
#include <vector>
using namespace std;
vector <pair<int, pair<int, int> > > a[200005];
vector <pair<int, pair<int, int> > >::iterator it;
vector<pair<int,int> > vs;
vector<pair<int,int> >::iterator it2;
pair <int, pair<int,int> > e;
priority_queue <
pair <int,pair<int,int> >,
vector <pair<int, pair<int,int> > >,
greater <pair<int, pair<int,int> > >
> q;
int i,j,m,n,c,x,y,v[200005],k=0,ct;
ofstream o("apm.out");
ifstream d("apm.in");

int main()
{

    d>>n>>m;
    for (i=1;i<=m;i++)
      {
        d>>x>>y>>c;
        a[x].push_back(make_pair(c,make_pair(x,y)));
        a[y].push_back(make_pair(c,make_pair(y,x)));
      }

    for (it=a[1].begin(); it!=a[1].end(); ++it)
      {
          q.push(*it);
      }

    v[1]=1;

    while (k<n-1)
    {
        e=q.top();
        q.pop();
        if (v[e.second.second]==0)
        {
            k++;
            e.second.second=1;
            vs.push_back(e.second);
            ct+=e.first;
            for(it=a[e.second.second].begin(); it!=a[e.second.second].end(); ++it)
            {
                q.push(*it);
            }
        }
    }

    o<<ct<<"\n"<<k<<"\n";
    for (it2=vs.begin(); it2!=vs.end(); ++it2)
    {
        o<<(*it2).first<<" "<<(*it2).second<<"\n";
    }

}