#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int INF = INT_MAX;
int n,M,x,y,i,c;
long long cost_total;
int main()
{
  f>>n>>M;
   vector<vector<pair<int,int>>> m(n+1);
   for(i=0;i<M;++i)
   {
       f>>x>>y>>c;
       m[x].push_back(make_pair(y,c));
       m[y].push_back(make_pair(x,c));
   }
   vector<int> dist(n+1, INF) , parent(n+1,-1);
   vector<bool> used (n+1,false);

   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
   int start=1;
   dist[start]=0;
   pq.push({0,start});

   while(!pq.empty())
   {
       int nod =pq.top().second;
       int cost =pq.top().first;
       pq.pop();
       if(used[nod])
        continue;
        used[nod]=true;
        cost_total+=cost;
       for(auto [vecin, c]: m[nod])
       {
           if(!used[vecin]&& c<dist[vecin])
           {
               dist[vecin]=c;
               parent[vecin] =nod;
               pq.push({c,vecin});


           }
       }
   }
   g<<cost_total<<endl;
   g<<n-1<<endl;
   for(i=1;i<=n;++i)
   {
       if(parent[i]!=-1)
        g<<parent[i]<<' '<<i<< endl;
   }



    return 0;
}