#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mp make_pair
#define CHECK(x) if(!(x)) return false;
#define CHECKRET(x, y) if(!(x)) return (y);
#define SKIP(x) if((x)) continue;
typedef pair<int, int> pii;

#ifdef INFOARENA
#define ProblemName "apm"
#else
#define ProblemName "fis"
#endif

#define InFile ProblemName ".in"
#define OuFile ProblemName ".out"

const int MAXN = 200010;
const int MAXM = 400010;

vector<int> G[MAXN];
bool inComp[MAXN];
pair<int, pii> edges[MAXM];
int N, M;

struct comp {
  bool operator()(int i, int j) {
    return edges[i] > edges[j];
  }
};

priority_queue<int, vector<int>, comp> Q;

void addNode(int x) {
  inComp[x] = true;
  for (const auto &m_id : G[x]) {
    int to = (edges[m_id].second.first == x) ? edges[m_id].second.second : edges[m_id].second.first;
    SKIP(inComp[to]);
    Q.push(m_id);
  }
}

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  scanf("%d%d", &N, &M);
  for (int i = 0; i < M; ++i) {
    scanf("%d%d%d", &edges[i].second.first, &edges[i].second.second, &edges[i].first);
    --edges[i].second.first, --edges[i].second.second;
    G[edges[i].second.first].push_back(i);
    G[edges[i].second.second].push_back(i);
  }
  addNode(0);
  int ans = 0;
  vector<int> sol;
  while (!Q.empty()) {
    int m_id = Q.top(); Q.pop();
    int to = -1;
    if (!inComp[edges[m_id].second.first]) to = edges[m_id].second.first;
    else if (!inComp[edges[m_id].second.second]) to = edges[m_id].second.second;
    SKIP(to < 0);
    sol.push_back(m_id);
    ans += edges[m_id].first;
    addNode(to);
  }
  printf("%d\n%d\n", ans, (int)sol.size());
  for (const auto &it : sol)
    printf("%d %d\n", edges[it].second.first + 1, edges[it].second.second + 1);
  return 0;
}