古老的贝尔兰有 n 个城市和 m 条道路。每条道路连接一对不同的城市并且是双向的。任何一对城市之间最多只有一条路。对于每条路,我们都知道它的长度。
我们还知道总统很快就会沿着 Berland 公路从 s 市骑行到 t 市。自然地,他会选择从 s 到 t 的最短路径之一,但没有人能确定他会选择哪条路径。
交通部长真的担心总统可能会对国家的道路状况感到不安。这就是他计划修复可能的总统道路上的道路的原因。
为这样的活动制定预算并不是一件容易的事。对于所有可能的不同对 s, t (s < t),找到位于从 s 到 t 的至少一条最短路径上的道路数量。
输入
输入的第一行包含整数 n, m (2 ≤ n ≤ 500, 0 ≤ m ≤ n·(n - 1) / 2) — 相应的城市和道路的数量。接下来是 m 行,包含道路描述,每行一个描述。每个描述包含三个整数xi,yi,li(1≤xi,yi≤n,xi≠yi,1≤li≤106),其中xi,yi是第i条路连接的城市的编号,li是它的长度。
输出
打印 $$n(n-1)/2$$ 整数 c12, c13, ..., c1n, c23, c24, ..., c2n, ..., cn - 1, n 的序列,其中 cst 是从 s 到 t 的最短路径上的道路数量。按所描述的顺序打印序列 c 的元素。如果城市对 s 和 t 之间没有路径,则 cst = 0。
示例
输入 #1
5 6 1 2 1 2 3 1 3 4 1 4 1 1 2 4 2 4 5 4
输出 #1
1 4 1 2 1 5 6 1 2 1