给定一张有向图, 有 $N$ 个点, $M$ 条单向边.

第 $i$ 条边是从 $A_i$ 到 $B_i$, 长 $C_i$.

定义 $f(s,t,k)$ 为只能经过编号小于 $k$ 或等于 $s$ 或等于 $t$ 的点的前提下， $s$ 到 $t$ 的最短路径长度。
特别的，如果 $s=t$ 或不存在 $s$ 到 $t$ 的路径, 有 $f(s,t,k)=0$.

输出 $\sum_{s=1}^N\sum_{t=1}^N\sum_{k=1}^N f(s,t,k)$

第一行两个整数 $N,M$

接下来 $M$ 行, 每行三个整数, 表示 $A_i, B_i, C_i$

• $1\le N\le 400$
  
• $0\le M\le N(N-1)$
  
• $1\le A_i, B_i\le N$
  
• $1\le C_i\le 10^6$
  
• 无重边自环
  

行一个整数, 表示答案

2022-cccc-xtsc