所有有序点对距离和

难度：T4

【知识点：Floyd全源最短路】

前置知识：Floyd全源最短路及其冻结前置单元。

题目描述与输入

第一行 $n$ $m$，随后 $m$ 行有向边 $u$ $v$ $w$。计算所有可达有序点对($i,j$)的最短距离总和，自身距离为$0$。

输出

输出总和。不可达的点对不计入。

数据范围

$1 \le n \le 80$，$0 \le m \le 500$，$1 \le w \le 10$。有向图，允许重边自环。

样例输入

3 3
1 2 4
2 3 2
1 3 10

样例输出

12

样例说明

可达非自身点对距离为$4$、$6$、$2$，总和$12$。