CF416E.President's Path

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.

古老的贝尔兰有 $n$ 座城市和 $m$ 条道路。每条道路连接一对不同的城市，且是双向的。任意两座城市之间至多只有一条道路。对于每条道路，我们已知其长度。

我们还知道，总统即将从城市 $s$ 沿贝尔兰的道路前往城市 $t$。显然，他将选择一条从 $s$ 到 $t$ 的最短路径，但没人能确定他会选择哪一条。

交通部长非常担心总统可能因国内道路的糟糕状况而感到不满。因此，他计划对总统可能经过的路径上的道路进行维修。

为这一事件制定预算是件不容易的事。请对所有满足 $s < t$ 的不同城市对 $(s, t)$，求出至少位于一条从 $s$ 到 $t$ 的最短路径上的道路数量。

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 x__i, y__i, l__i (1 ≤ x__i, y__i ≤ n, x__i ≠ y__i, 1 ≤ l__i ≤ 106), where x__i, y__i are the numbers of the cities connected by the i-th road and l__i is its length.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 500$，$0 \leq m \leq n \cdot (n - 1) / 2$），分别表示城市的数量和道路的数量。接下来的 $m$ 行每行描述一条道路，共 $m$ 行。每行包含三个整数 $x_i,\ y_i,\ l_i$（$1 \leq x_i,\ y_i \leq n$，$x_i \neq y_i$，$1 \leq l_i \leq 10^6$），其中 $x_i$ 和 $y_i$ 表示第 $i$ 条道路所连接的两座城市的编号，$l_i$ 表示该道路的长度。

Print the sequence of integers _c_12, _c_13, ..., c_1_n, _c_23, _c_24, ..., c_2_n, ..., c__n - 1, n, where c__st 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 c__st = 0.

输出长度为 $\frac{n(n-1)}{2}$ 的整数序列 $c_{12},\ c_{13},\ \dots,\ c_{1n},\ c_{23},\ c_{24},\ \dots,\ c_{2n},\ \dots,\ c_{n-1,n}$，其中 $c_{st}$ 表示在从城市 $s$ 到城市 $t$ 的最短路径中可能经过的道路数量。请按上述顺序输出序列 $c$ 的各项。若城市 $s$ 与城市 $t$ 之间不存在路径，则令 $c_{st} = 0$。