#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

int main()
{
     int n,m;
     in>>n>>m;
     int inf=1<<24;
     set<pair<int,pair<int,int>>> S;
     vector <int> viz(n+1,0);
     vector <pair<int,int>> Dist(n+1);
     vector<vector<pair<int,int>>>Graf(n+1);
     vector<int> Minim(n+1,inf);
     vector<pair<int,int>> tati(n+1);
     for(int i=0;i<m;i++)
     {
         int x,y,c;
         in>>x>>y>>c;
         Graf[x].push_back({c,y});
         Graf[y].push_back({c,x});
     }
     int nod_start=1;
     viz[nod_start]=1;
     int k=1;
     for(auto i:Graf[nod_start])
     {
         S.insert({i.first,{nod_start,i.second}});
     }
     long long cost=0;
     while(k<n)
     {
         pair<int,pair <int,int>> p=(*S.begin());
         S.erase(S.begin());
         if(viz[p.second.second]==0)
         {
             viz[p.second.second]=1;
             tati[k]={p.second.first,p.second.second};
             cost=cost+p.first;
             k++;
             for(auto i:Graf[p.second.second])
             {
                 if(viz[i.second]==0)
                 {
                     S.insert({i.first,{p.second.second,i.second}});
                 }
             }
         }
     }
     out<<cost<<"\n";
     out<<n-1<<"\n";
     for(int i=1;i<n;i++)
        out<<tati[i].first<<" "<<tati[i].second<<"\n";


}