#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 9;
const long long INF = 1e18;
const int MAXN = 1e6 + 10;
const int MAXM = 1e4 + 500;
const int N = 500 + 15;
const double EPS = 1e-9;
int dx[] = {1, 0, 0, -1};
int dy[] = {0, 1, -1, 0};
double len(complex<long long> a) {
  return sqrt(a.real() * a.real() + a.imag() * a.imag());
}
long long sq(complex<long long> a) {
  return a.real() * a.real() + a.imag() * a.imag();
}
complex<long long> perp(complex<long long> p) { return {-p.imag(), p.real()}; }
long long dotProduct(complex<long long> a, complex<long long> b) {
  return (conj(a) * b).real();
}
long long crossProduct(complex<long long> a, complex<long long> b) {
  return (conj(a) * b).imag();
}
long long orient(complex<long long> a, complex<long long> b,
                 complex<long long> c) {
  return crossProduct(b - a, c - a);
}
bool inDisk(complex<long long> a, complex<long long> b, complex<long long> p) {
  return dotProduct(a - p, b - p) <= 0;
}
bool onSegment(complex<long long> a, complex<long long> b,
               complex<long long> p) {
  return orient(a, b, p) == 0 && inDisk(a, b, p);
};
struct cmpX {
  bool operator()(complex<long long> a, complex<long long> b) {
    return make_pair(a.real(), a.imag()) < make_pair(b.real(), b.imag());
  }
};
struct line {
  complex<long long> v;
  long long c;
  line(complex<long long> v, long long c) : v(v), c(c) {}
  line(long long a, long long b, long long c) : v({b, -a}), c(c) {}
  line(complex<long long> p, complex<long long> q)
      : v(q - p), c(crossProduct(v, p)) {}
  long long side(complex<long long> p) { return crossProduct(v, p) - c; }
  double dist(complex<long long> p) { return abs(side(p)) / len(v); }
  line perpThrough(complex<long long> p) { return {p, p + perp(v)}; }
  bool cmpProj(complex<long long> p, complex<long long> q) {
    return dotProduct(v, p) < dotProduct(v, q);
  }
  line translate(complex<long long> t) { return {v, c + crossProduct(v, t)}; }
  complex<long long> proj(complex<long long> p) {
    return p - perp(v) * side(p) / sq(v);
  }
};
double segPoint(complex<long long> a, complex<long long> b,
                complex<long long> p) {
  if (a != b) {
    line l(a, b);
    if (l.cmpProj(a, p) && l.cmpProj(p, b)) return l.dist(p);
  }
  return min(abs(p - a), abs(p - b));
}
bool inAngle(complex<long long> a, complex<long long> b, complex<long long> c,
             complex<long long> p) {
  if (orient(a, b, c) < 0) swap(b, c);
  return orient(a, b, p) >= 0 && orient(a, c, p) <= 0;
}
bool isInsidePol(vector<complex<long long> > &a, complex<long long> b) {
  int n = a.size();
  int pos = 0, neg = 0;
  for (int i = 0; i < n - 1; i++) {
    if (onSegment(a[i], a[(i + 1) % n], b)) return false;
    line l(a[i], a[i + 1]);
    if (l.side(b) > 0)
      pos++;
    else
      neg++;
  }
  line l(a[n - 1], a[0]);
  if (l.side(b) > 0)
    pos++;
  else
    neg++;
  return ((!pos && neg == n) || (!neg && pos == n));
}
long long i, j, k;
long long n, m, t;
vector<pair<int, int> > adj[N];
int dp[N][N], inEdge[N][N], c[N][N];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) dp[i][j] = 1e9;
  for (i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    dp[u][v] = dp[v][u] = w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  for (int first = 0; first < n; first++)
    for (int u = dp[first][first] = 0; u < n; u++)
      for (int v = 0; v < n; v++)
        dp[u][v] = min(dp[u][v], dp[u][first] + dp[first][v]);
  for (int source = 0; source < n; source++) {
    for (int v = 0; v < n; v++)
      for (auto e : adj[v]) {
        int to = e.first, w = e.second;
        inEdge[source][v] += (dp[source][to] + w == dp[source][v]);
      }
    for (int destination = 0; destination < n; destination++)
      for (int mid = 0; mid < n; mid++) {
        if (dp[source][mid] + dp[mid][destination] == dp[source][destination])
          c[source][destination] += inEdge[source][mid];
      }
    for (int v = source + 1; v < n; v++) cout << c[source][v] << ' ';
  }
  return 0;
}

### Prompt

Your task is to create a Cpp solution to the following problem:

Good old Berland has n cities and m roads. Each road connects a pair of distinct cities and is bidirectional. Between any pair of cities, there is at most one road. For each road, we know its length.

We also know that the President will soon ride along the Berland roads from city s to city t. Naturally, he will choose one of the shortest paths from s to t, but nobody can say for sure which path he will choose.

The Minister for Transport is really afraid that the President might get upset by the state of the roads in the country. That is the reason he is planning to repair the roads in the possible President's path.

Making the budget for such an event is not an easy task. For all possible distinct pairs s, t (s < t) find the number of roads that lie on at least one shortest path from s to t.

Input

The first line of the input contains integers n, m (2 ≤ n ≤ 500, 0 ≤ m ≤ n·(n - 1) / 2) — the number of cities and roads, correspondingly. Then m lines follow, containing the road descriptions, one description per line. Each description contains three integers xi, yi, li (1 ≤ xi, yi ≤ n, xi ≠ yi, 1 ≤ li ≤ 106), where xi, yi are the numbers of the cities connected by the i-th road and li is its length.

Output

Print the sequence of <image> integers c12, c13, ..., c1n, c23, c24, ..., c2n, ..., cn - 1, n, where cst is the number of roads that can lie on the shortest path from s to t. Print the elements of sequence c in the described order. If the pair of cities s and t don't have a path between them, then cst = 0.

Examples

Input

5 6
1 2 1
2 3 1
3 4 1
4 1 1
2 4 2
4 5 4


Output

1 4 1 2 1 5 6 1 2 1 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 9;
const long long INF = 1e18;
const int MAXN = 1e6 + 10;
const int MAXM = 1e4 + 500;
const int N = 500 + 15;
const double EPS = 1e-9;
int dx[] = {1, 0, 0, -1};
int dy[] = {0, 1, -1, 0};
double len(complex<long long> a) {
  return sqrt(a.real() * a.real() + a.imag() * a.imag());
}
long long sq(complex<long long> a) {
  return a.real() * a.real() + a.imag() * a.imag();
}
complex<long long> perp(complex<long long> p) { return {-p.imag(), p.real()}; }
long long dotProduct(complex<long long> a, complex<long long> b) {
  return (conj(a) * b).real();
}
long long crossProduct(complex<long long> a, complex<long long> b) {
  return (conj(a) * b).imag();
}
long long orient(complex<long long> a, complex<long long> b,
                 complex<long long> c) {
  return crossProduct(b - a, c - a);
}
bool inDisk(complex<long long> a, complex<long long> b, complex<long long> p) {
  return dotProduct(a - p, b - p) <= 0;
}
bool onSegment(complex<long long> a, complex<long long> b,
               complex<long long> p) {
  return orient(a, b, p) == 0 && inDisk(a, b, p);
};
struct cmpX {
  bool operator()(complex<long long> a, complex<long long> b) {
    return make_pair(a.real(), a.imag()) < make_pair(b.real(), b.imag());
  }
};
struct line {
  complex<long long> v;
  long long c;
  line(complex<long long> v, long long c) : v(v), c(c) {}
  line(long long a, long long b, long long c) : v({b, -a}), c(c) {}
  line(complex<long long> p, complex<long long> q)
      : v(q - p), c(crossProduct(v, p)) {}
  long long side(complex<long long> p) { return crossProduct(v, p) - c; }
  double dist(complex<long long> p) { return abs(side(p)) / len(v); }
  line perpThrough(complex<long long> p) { return {p, p + perp(v)}; }
  bool cmpProj(complex<long long> p, complex<long long> q) {
    return dotProduct(v, p) < dotProduct(v, q);
  }
  line translate(complex<long long> t) { return {v, c + crossProduct(v, t)}; }
  complex<long long> proj(complex<long long> p) {
    return p - perp(v) * side(p) / sq(v);
  }
};
double segPoint(complex<long long> a, complex<long long> b,
                complex<long long> p) {
  if (a != b) {
    line l(a, b);
    if (l.cmpProj(a, p) && l.cmpProj(p, b)) return l.dist(p);
  }
  return min(abs(p - a), abs(p - b));
}
bool inAngle(complex<long long> a, complex<long long> b, complex<long long> c,
             complex<long long> p) {
  if (orient(a, b, c) < 0) swap(b, c);
  return orient(a, b, p) >= 0 && orient(a, c, p) <= 0;
}
bool isInsidePol(vector<complex<long long> > &a, complex<long long> b) {
  int n = a.size();
  int pos = 0, neg = 0;
  for (int i = 0; i < n - 1; i++) {
    if (onSegment(a[i], a[(i + 1) % n], b)) return false;
    line l(a[i], a[i + 1]);
    if (l.side(b) > 0)
      pos++;
    else
      neg++;
  }
  line l(a[n - 1], a[0]);
  if (l.side(b) > 0)
    pos++;
  else
    neg++;
  return ((!pos && neg == n) || (!neg && pos == n));
}
long long i, j, k;
long long n, m, t;
vector<pair<int, int> > adj[N];
int dp[N][N], inEdge[N][N], c[N][N];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) dp[i][j] = 1e9;
  for (i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    dp[u][v] = dp[v][u] = w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  for (int first = 0; first < n; first++)
    for (int u = dp[first][first] = 0; u < n; u++)
      for (int v = 0; v < n; v++)
        dp[u][v] = min(dp[u][v], dp[u][first] + dp[first][v]);
  for (int source = 0; source < n; source++) {
    for (int v = 0; v < n; v++)
      for (auto e : adj[v]) {
        int to = e.first, w = e.second;
        inEdge[source][v] += (dp[source][to] + w == dp[source][v]);
      }
    for (int destination = 0; destination < n; destination++)
      for (int mid = 0; mid < n; mid++) {
        if (dp[source][mid] + dp[mid][destination] == dp[source][destination])
          c[source][destination] += inEdge[source][mid];
      }
    for (int v = source + 1; v < n; v++) cout << c[source][v] << ' ';
  }
  return 0;
}

```