#include <bits/stdc++.h>
using namespace std;
int min(int x, int y) {
  if (x < y) return x;
  return y;
}
int d[100][100][3];
int main(void) {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < 100; i++) {
    for (int j = 0; j < 100; j++) {
      if (i != j) {
        d[i][j][0] = 1e9 + 7;
        d[i][j][1] = 1e9 + 7;
        d[i][j][2] = 0;
      } else {
        d[i][j][0] = 0;
        d[i][j][1] = 0;
        d[i][j][2] = 0;
      }
    }
  }
  for (int i = 0; i < m; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    a--;
    b--;
    d[a][b][0] = c;
    d[b][a][0] = c;
    d[a][b][1] = c;
    d[b][a][1] = c;
    d[a][b][2] = 1;
    d[b][a][2] = 1;
  }
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        d[i][j][0] = min(d[i][j][0], d[i][k][0] + d[k][j][0]);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) {
        if (d[i][j][0] == d[i][k][0] + d[j][k][1]) d[j][k][2] = 0;
      }
    }
  }
  int count = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (d[i][j][2] == 1) count++;
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      printf("%d ", d[i][j][0]);
    }
    printf("\n");
  }
  printf("%d\n", count / 2);
  return 0;
}
