#include<fstream>
#include<queue>
#include<vector>
#include<ctime>
#include<algorithm>
#define NMAX 200001
#define MMAX 400001

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct pereche
{
    int val;
    short cost;
};

class muchie
{
public:
    int first,second;
    short cost;
    friend bool operator<(muchie m1,muchie m2);

};

bool operator<(muchie m1,muchie m2)
{
    if(m1.cost<m2.cost)
        return false;
    return true;
}

vector<pereche> v[NMAX];
bool noduri[NMAX];
vector<muchie> solutii;
priority_queue<muchie> heap;
int n,m,i,nrMuchii,nod,aux2;
long long cost;
muchie muc;

void solve()
{
  pereche aux;
  do
  {
     for(i=0;i<v[nod].size();i++)
     {
         aux=v[nod][i];
         muc.first=nod; muc.second=aux.val; muc.cost=aux.cost; // g<<muc.first<<" "<<muc.second<<" "<<muc.cost<<'\n';
         heap.push(muc);
     }

 //    g<<aux2<<'\n';

     while(!heap.empty())
     {
        aux2=(heap.top()).second;
        if(noduri[aux2]==1)
          {heap.pop();aux2=(heap.top()).second;}
        else
           break;
     }

     if(!heap.empty()){
       muc=heap.top(); heap.pop();
       cost+=muc.cost; nrMuchii++;
       solutii.push_back(muc);
       noduri[muc.second]=1;
       nod=muc.second;
     }
  }while(!heap.empty());

}

int main()
{
    srand(time(0));
    int x,y,c;
    muchie edge;
    pereche per1,per2;

    f>>n>>m;

    for(i=0;i<m;i++)
    {
        f>>x>>y>>c;
        per1.val=x;per2.val=y;
        per1.cost=per2.cost=c;
        v[x].push_back(per2); v[y].push_back(per1);
    }
    nod=x;
    noduri[nod]=1;
    solve();
    g<<cost<<'\n'<<nrMuchii<<'\n';

    for(i=0;i<solutii.size();i++)
    {
        muc=solutii[i];
        g<<muc.first<<" "<<muc.second<<'\n';
    }

    f.close();g.close();
    return 0;
}