#pragma GCC optimize("Ofast")
#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 MAXBUF = 30000000;
char parseBuf[MAXBUF];
char *head;
bool isDigit[255];

void parseInit() {
  int a = fread(parseBuf, 1, MAXBUF, stdin);
  parseBuf[a] = 0;
  head = parseBuf;
  memset(isDigit, 0, sizeof isDigit);
  for (int i = '0'; i <= '9'; ++i)
    isDigit[i] = true;
  isDigit['-'] = true;
}

int nextInt() {
  int ans = 0;
  for (; !isDigit[(int)*head]; ++head);
  int sgn = 1;
  if (*head == '-')
    sgn = -1, ++head;
  for (; isDigit[(int)*head]; ++head)
    ans = ans * 10 + (*head) - '0';
  return ans * sgn;
}

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 {
  inline 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));
  parseInit();
  N = nextInt(), M = nextInt();
  for (int i = 0; i < M; ++i) {
    edges[i].second.first = nextInt(), edges[i].second.second = nextInt(), 
      edges[i].first = nextInt();
    --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 = edges[m_id].second.first;
    if (inComp[to]) to = edges[m_id].second.second;
    SKIP(inComp[to]);
    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;
}