A72007 | 子图最短路

给定包含 n 个结点 m 条边的带权无向图 G，结点依次以 1, 2, \dots, 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 取模的结果。