#include <bits/stdc++.h>
using namespace std;
const int MAXN = 101;
const int INF = 0x3f3f3f3f;
const int NIL = -1;
int matrix[MAXN][MAXN];
int nextV[MAXN][MAXN];
set<pair<int, int>> yee;
pair<int, int> edge(int a, int b) { return make_pair(min(a, b), max(a, b)); }
void process(pair<int, int> edge) {
  if (edge.first != edge.second) {
    yee.insert(edge);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  int u, v, w;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
      matrix[i][j] = INF;
      nextV[i][j] = NIL;
      if (i == j) {
        matrix[i][j] = 0;
      }
    }
  }
  for (int i = 0; i < m; i++) {
    cin >> u >> v >> w;
    matrix[u][v] = w;
    matrix[v][u] = w;
    nextV[u][v] = v;
    nextV[v][u] = u;
    yee.insert(edge(u, v));
  }
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        int newlength = matrix[i][k] + matrix[k][j];
        if (matrix[i][j] > newlength) {
          matrix[i][j] = newlength;
          yee.erase(edge(i, nextV[i][j]));
          cout << i << ' ' << nextV[i][j] << " replaced by ";
          nextV[i][j] = nextV[i][k];
          process(edge(i, nextV[i][k]));
          cout << i << ' ' << nextV[i][k] << endl;
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cout << nextV[i][j] << ' ';
    }
    cout << endl;
  }
  cout << m - yee.size() << endl;
  return 0;
}
