Z国有 $N$ 座城市和 $M$ 条道路。

城市编号为 $1$ 至 $N$ ，道路编号为 $1$ 至 $M$ 。道路 $i$ 是一条从城市 $A_i$ 通往城市 $B_i$ 的**单向**道路，通过这条道路需要 $C_i$ 分钟。

让我们将 $f(s, t, k)$ 定义为以下问题的答案。

- 计算从城市 $s$ 到城市 $t$ 所需的最短时间。在这里，除了城市 $s$ 和 $t$ 之外，只允许经过城市 $1$ 到 $k$ 。如果城市 $t$ 无法到达或 $s = t$ 无法到达，那么答案应该是 $0$ 。

计算所有三元组 $s,t,k$ 的 $f(s,t,k)$ 并打印它们的总和。更正式地说，输出$\displaystyle \sum_{s = 1}^N \sum_{t = 1}^N \sum_{k = 1}^N f(s, t, k)$ 。

第一行两个数 $n,m$。

接下来 $m$ 行，每行三个数 $u_i,v_i,w_i$，表示一条从 $u_i$ 到 $v_i$，权值为 $w_i$ 的单向边。

最短路径的总和

- $1 \leq N \leq 400$

- $0 \leq M \leq N(N-1)$

- $1 \leq A_i \leq N$ $(1 \leq i \leq M)$

- $1 \leq B_i \leq N$ $(1 \leq i \leq M)$

- $A_i \neq B_i$ $(1 \leq i \leq M)$

- $1 \leq C_i \leq 10^6$ $(1 \leq i \leq M)$

- $A_i \neq A_j$ 或 $B_i \neq B_j$ ，如果是 $i \neq j$ 。

- 输入值均为整数。

样例说明：

$s,t,k$ 这样的三元组 $f(s,t,k) \neq 0$ 如下。

- 对于 $k = 1$ ： $f(1,2,1) = 3, f(2,3,1) = 2$ .

- 对于 $k = 2$ ： $f(1,2,2) = 3, f(2,3,2) = 2, f(1,3,2) = 5$ .

- 对于 $k = 3$ ： $f(1,2,3) = 3, f(2,3,3) = 2, f(1,3,3) = 5$ .