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


using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
vector <int> graph[50005];
vector <int> graphC[50005];
priority_queue<pair<int,pair<int,int> > >myheap;
vector<pair<int,int> > muchii;
int viz[50005];

#define max_size 20000005


int main()
{
    int N,M,x,y,c,i,k;
    int cost=0,nr_m=0;
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y>>c;
        graph[x].push_back(y);
        graphC[x].push_back(c);
        graph[y].push_back(x);
        graphC[y].push_back(c);
    }
   viz[1]=1;
   for(i=0;i<graph[1].size();i++)
    myheap.push(make_pair((-1)*graphC[1][i],make_pair(1,graph[1][i])));
   while(!myheap.empty())
     {
          pair<int,int>muchie;
          pair<int, pair<int, int> > p = myheap.top();
          myheap.pop();
          muchie=p.second;
          if((viz[muchie.first]==1)&&(viz[muchie.second]==1));
           else{
             viz[muchie.first]=1;
             viz[muchie.second]=1;

            for(int k=0;k<graph[muchie.second].size();k++)
                myheap.push(make_pair((-1)*graphC[muchie.second][k],make_pair(muchie.second,graph[muchie.second][k])));


            muchii.push_back(make_pair(muchie.first,muchie.second));
            cost+=(-1)*p.first;
            nr_m++;


           }

     }


    fout<<cost<<endl<<nr_m<<endl;
     for(i=0;i<muchii.size();i++)
        fout<<muchii[i].first<<" "<<muchii[i].second<<endl;

    return 0;
}