#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
using Int = long long;
constexpr int mod = 1e9 + 7;
constexpr int INF32 = numeric_limits<int>::max();
constexpr Int INF64 = numeric_limits<Int>::max();
template <class T>
inline bool cmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool cmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
int n, m, _, x, y, q;
string s, sb;
bool ok;
char cf, cb;
template <int MOD>
struct ModInt {
  static const int Mod = MOD;
  unsigned x;
  ModInt() : x(0) {}
  ModInt(signed sig) {
    int sigt = sig % MOD;
    if (sigt < 0) sigt += MOD;
    x = sigt;
  }
  ModInt(signed long long sig) {
    int sigt = sig % MOD;
    if (sigt < 0) sigt += MOD;
    x = sigt;
  }
  int get() const { return (int)x; }
  ModInt &operator+=(ModInt that) {
    if ((x += that.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator-=(ModInt that) {
    if ((x += MOD - that.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator*=(ModInt that) {
    x = (unsigned long long)x * that.x % MOD;
    return *this;
  }
  ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
  ModInt &operator%=(ModInt that) {
    x %= that.x;
    return *this;
  }
  ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
  ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
  ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
  ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
  ModInt operator%(ModInt that) const { return ModInt(*this) %= that; }
  ModInt inverse() const {
    signed a = x, b = MOD, u = 1, v = 0;
    while (b) {
      signed t = a / b;
      a -= t * b;
      std::swap(a, b);
      u -= t * v;
      std::swap(u, v);
    }
    if (u < 0) u += Mod;
    ModInt res;
    res.x = (unsigned)u;
    return res;
  }
  bool operator==(ModInt that) const { return x == that.x; }
  bool operator!=(ModInt that) const { return x != that.x; }
  ModInt operator-() const {
    ModInt t;
    t.x = x == 0 ? 0 : Mod - x;
    return t;
  }
  friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; }
  friend istream &operator>>(istream &is, ModInt &a) {
    int t;
    is >> t;
    a = ModInt<mod>(t);
    return (is);
  }
};
template <int MOD>
ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
  ModInt<MOD> r = 1;
  while (k) {
    if (k & 1) r *= a;
    a *= a;
    k >>= 1;
  }
  return r;
}
vector<ModInt<mod>> fact, factinv;
void COMinit(int N) {
  N = min(N, ModInt<mod>::Mod - 1);
  fact.resize(N + 1);
  factinv.resize(N + 1);
  fact[0] = 1;
  for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i;
  factinv[N] = fact[N].inverse();
  for (int i = N; i >= 1; i--) factinv[i - 1] = factinv[i] * i;
}
ModInt<mod> C(int n, int r) {
  if (n >= ModInt<mod>::Mod)
    return C(n % ModInt<mod>::Mod, r % ModInt<mod>::Mod) *
           C(n / ModInt<mod>::Mod, r / ModInt<mod>::Mod);
  return r > n ? 0 : fact[n] * factinv[n - r] * factinv[r];
}
template <class T>
struct edge {
  int fr, to;
  T w;
  edge(int to, T w) : fr(-1), to(to), w(w) {}
  edge(int fr, int to, T w) : fr(fr), to(to), w(w) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template <typename T>
using Matrix = vector<vector<T>>;
template <class T>
vector<T> rev_dijkstra(WeightedGraph<T> &g, int s) {
  const auto INF = numeric_limits<T>::max();
  vector<T> dist(g.size(), INF);
  using Pi = pair<T, int>;
  priority_queue<Pi, vector<Pi>, greater<Pi>> que;
  dist[s] = 0;
  que.emplace(dist[s], s);
  while (!que.empty()) {
    T cost;
    int idx;
    tie(cost, idx) = que.top();
    que.pop();
    if (dist[idx] < cost) continue;
    for (auto &e : g[idx]) {
      auto next_cost = cost + e.w;
      if (dist[e.to] <= next_cost) continue;
      dist[e.to] = next_cost;
      que.emplace(dist[e.to], e.to);
    }
  }
  return dist;
}
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(0);
  cin >> n >> m;
  WeightedGraph<int> g(n);
  map<pair<int, int>, bool> used;
  Edges<int> ed;
  for (int i = (0); i < (m); ++i) {
    cin >> x >> y >> q;
    x--;
    y--;
    used[pair<int, int>(x, y)] = 0;
    used[pair<int, int>(y, x)] = 0;
    g[x].emplace_back(y, q);
    g[y].emplace_back(x, q);
    ed.emplace_back(x, y, q);
    ed.emplace_back(y, x, q);
  }
  vector<vector<int>> d(n);
  for (int i = (0); i < (n); ++i) d[i] = rev_dijkstra(g, i);
  int ans = 0;
  for (int i = (0); i < (n); ++i) {
    for (int j = (0); j < (n - 1); ++j) cout << d[i][j] << ' ';
    if (n) cout << d[i][n - 1] << '\n';
  };
  for (int i = (0); i < (n); ++i) {
    for (auto e : ed) {
      if (d[i][e.fr] + e.w == d[i][e.to]) used[pair<int, int>(e.fr, e.to)] = 1;
    }
  }
  for (auto e : used) ans += e.second ^ 1;
  ans /= 2;
  {
    cout << ans << '\n';
    return 0;
  }
}
