#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const bool test = false;
long long dx[] = {1, 0, -1, 0};
long long dy[] = {0, 1, 0, -1};
const long long INF = (long long)1 << 60;
const ll INFL = (ll)1 << 60;
ll mod_n = (long long)1e9 + 7;
const double eps = 1e-10;
long long sgn(const long double &r) { return (r > eps) - (r < -eps); }
long long sgn(const long double &a, const long double &b) { return sgn(a - b); }
const long long MAX = (long long)2e5 + 5;
vector<string> split(const string &str, char sep) {
  vector<string> v;
  stringstream ss(str);
  string buffer;
  while (getline(ss, buffer, sep)) {
    v.push_back(buffer);
  }
  return v;
}
template <class InputIterator>
long long sum(InputIterator begin, InputIterator end) {
  return accumulate(begin, end, 0ll);
}
void solve();
signed main() {
  cout << fixed << setprecision(20);
  solve();
  return 0;
}
struct Edge {
  long long from, to, weight;
};
long long N, M;
vector<Edge> graph;
vector<vector<long long>> d;
long long connect1[MAX];
void warshall_floyd() {
  long long i, j, k;
  cin >> N >> M;
  d.resize(N + 1);
  for (long long i = 0; i < (d.size()); ++i) d[i].resize(N + 1);
  for (long long i = 0; i < (N); ++i)
    for (long long j = 0; j < (N); ++j) d[i][j] = INF;
  for (long long i = 0; i < (N); ++i) d[i][i] = 0;
  long long n = N;
  for (long long i = 0; i < (M); ++i) {
    long long v, u, l;
    cin >> u >> v >> l;
    u--;
    v--;
    graph.push_back({u, v, l});
    d[u][v] = l;
    d[v][u] = l;
  }
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      for (k = 0; k < n; k++) d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
}
void solve() {
  warshall_floyd();
  long long res = 0;
  for (long long i = 0; i < (N); ++i) {
    for (long long j = 0; j < (N); ++j) cout << d[i][j] << " ";
    cout << endl;
  }
  for (long long id = 0; id < (M); ++id) {
    long long i = graph[id].from;
    long long j = graph[id].to;
    bool flag = true;
    for (long long s = 0; s < (N); ++s)
      for (long long g = 0; g < (N); ++g) {
        if (d[s][i] + graph[id].weight + d[j][g] == d[s][g]) flag = false;
      }
    if (flag) {
      ;
      ;
      ;
      res++;
    }
  }
  cout << res << endl;
}
