#include <iostream>
#include <queue>
#include <fstream>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,cost,sel[200001],i,x,y;
vector <pair<int,int> > g[200001];
vector <pair <int,int > > h;
typedef pair<int, pair <int,int > > pi;
pi k;
priority_queue <pi,vector<pi>,greater<pi> > Q;
void prim (int x)
{
   sel[x]=true;
   for (auto i:g[x]) Q.push({i.first,{x,i.second}});
   for (int i=1;i<n;++i)
   {
      while (!Q.empty()&&sel[Q.top().second.second]) Q.pop();
      k=Q.top(); cost+=k.first;
      sel[k.second.second]=true;
      h.push_back({k.second.first,k.second.second});
      for (auto j:g[k.second.second])
      if (!sel[j.second])
          Q.push({j.first,{k.second.second,j.second}});
   }
}
int main()
{
   in>>n>>m;
   for (i=1;i<=m;++i)
   {
      in>>x>>y>>cost;
      g[x].push_back({cost,y});
      g[y].push_back({cost,x});
   }
   cost=0;
   prim(1);
   out<<cost<<'\n'<<n-1<<'\n';
   for (i=0;i<n-1;++i)
   {
      out<<h[i].first<<" "<<h[i].second<<'\n';
   }
    return 0;
}