#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#define NMAX 200005

using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

int N, M, a, b, c, parent[NMAX], min_edge[NMAX];
long long ans;
bool visited[NMAX];

priority_queue < pair <int, int> , vector < pair <int, int> > , greater < pair <int, int> > > pq;

vector < pair <int, int> >G[NMAX];
vector < pair <int, int> > mst;

void prim(int x)
{
  visited[x] = 1;
  for(auto e : G[x]){
      pq.push({e.second, e.first});
      parent[e.first] = 1;
      min_edge[e.first] = e.second;
  }

  while(pq.size())
  {
    int acc = pq.top().second;
    int w = pq.top().first;
    pq.pop();
    if(!visited[acc])
    {
      ans += w;
      visited[acc] = 1;
      mst.push_back({acc, parent[acc]});
      for(auto e : G[acc])
        if(!visited[e.first]){
            pq.push({e.second, e.first});
            if(parent[e.first]){
              if(min_edge[e.first] > e.second){
                parent[e.first] = acc;
              }
            }
            else{
              parent[e.first] = acc;
              min_edge[e.first] = e.second;
            }
        }
    }
  }

}


int main()
{
  cin >> N >> M;
  for(int i = 1; i <= M; i++){
    cin >> a >> b >> c;
    G[a].push_back({b, c});
    G[b].push_back({a, c});
  }

  prim(1);

  cout << ans << '\n';
  cout << mst.size() << '\n';
  for(auto e : mst)
    cout << e.first << ' ' << e.second << '\n';
  return 0;
}