#include <bits/stdc++.h>
using namespace std;
int n, m, u, v, i, j, d[500], to, c, e[500];
bitset<500> ans[500], b;
bool used[500];
vector<pair<int, int> > g[500];
bitset<500> getAns(int v) {
  if (used[v]) return ans[v];
  used[v] = true;
  ans[v][v] = 1;
  for (int i = 0; i < g[v].size(); i++) {
    int to = g[v][i].first, dist = g[v][i].second;
    if (d[to] + dist == d[v]) ans[v] |= getAns(to);
  }
  return ans[v];
}
int main() {
  ios_base ::sync_with_stdio(0);
  cin.tie();
  cin >> n >> m;
  for (i = 0; i < m; i++) {
    cin >> u >> v >> c;
    u--;
    v--;
    g[u].push_back({v, c});
    g[v].push_back({u, c});
  }
  for (u = 0; u < n; u++) {
    fill(d, d + n, 1000000000);
    fill(used, used + n, false);
    d[u] = 0;
    for (j = 0; j < n; j++) {
      v = -1;
      for (i = 0; i < n; i++) {
        if (!used[i] && (v == -1 || d[i] < d[v])) v = i;
      }
      if (v == -1 || d[v] == 1000000000) break;
      used[v] = true;
      for (i = 0; i < g[v].size(); i++) {
        int to = g[v][i].first, dist = g[v][i].second;
        if (d[to] > d[v] + dist) {
          d[to] = d[v] + dist;
        }
      }
    }
    fill(e, e + n, 0);
    for (v = 0; v < n; v++) {
      for (j = 0; j < g[v].size(); j++) {
        int to = g[v][j].first, dist = g[v][j].second;
        if (d[v] == d[to] + dist) e[v]++;
      }
    }
    fill(ans, ans + n, 0);
    fill(used, used + n, false);
    for (i = u + 1; i < n; i++) {
      b = getAns(i);
      int cnt = 0;
      for (j = 0; j < n; j++) {
        if (b[j]) cnt += e[j];
      }
      cout << cnt << " ";
    }
  }
  return 0;
}
