子图最短路

题目描述

给定包含 $n$ 个结点 $m$ 条边的带权无向图 $G$，结点依次以 $1,2,\ldots,n$ 编号。第 $i$（$1\le i\le m$）条边连接编号为 $u_i$ 与 $v_i$ 的两个结点，权值为 $w_i$。

对于指定的 $1\le\ell\le r\le n$，按以下方式构造图 $G$ 的子图 $G(\ell,r)$：

• 保留 $G$ 中编号在区间 $[\ell,r]$ 中的结点。删去其它编号不在 $[\ell,r]$ 中的结点以及与之相连的边。剩余的结点和边构成子图 $G(\ell,r)$。

对于 $G(\ell,r)$ 中的任意结点 $u,v$ 应有 $\ell\le u,v\le r$。记 $u,v$ 在子图 $G(\ell,r)$ 上的最短距离为 $d(\ell,r,u,v)$。特殊地，若 $u,v$ 在子图 $G(\ell,r)$ 上不连通，则认为 $d(\ell,r,u,v)=0$。

你需要求出 $\sum_{\ell=1}^{n}\sum_{r=\ell}^{n}\sum_{u=\ell}^{r}\sum_{v=u}^{r}d(\ell,r,u,v)$ 对 $10^9$ 取模的结果。

• 题目中的英文字母 $l$ 使用了特殊写法 $\ell$，以避免英文字母 $l$ 与数字 $1$ 混淆。

输入格式

第一行，两个正整数 $n,m$，表示结点数与边数。

接下来 $m$ 行，第 $i$（$1\le i\le m$）行包含三个正整数 $u_i,v_i,w_i$，表示一条连接结点 $u_i,v_i$ 的权值为 $w_i$ 的边。

输出格式

输出一行，一个整数，表示 $\sum_{\ell=1}^{n}\sum_{r=\ell}^{n}\sum_{u=\ell}^{r}\sum_{v=u}^{r}d(\ell,r,u,v)$ 对 $10^9$ 取模的结果。

输入样例 1

13 221 2 132 3 2

输出样例 1

19

输入样例 2

14 621 2 10032 3 10043 4 10051 3 1062 4 1071 4 1

输出样例 2

1784

数据范围

对于 $40\%$ 的测试点，保证 $2\le n\le 20$。

对于所有测试点，保证 $2\le n\le 100$，$2\le m\le\frac{n(n-1)}{2}$，$1\le u_i,v_i\le n$，$1\le w_i\le 10^6$。图中可能存在重边。