背景

GESP八级真题(2603)

描述

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

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

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

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

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

格式

输入

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

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

输出

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

样例

3 2
1 2 1
2 3 2

9

4 6
1 2 100
2 3 100
3 4 100
1 3 10
2 4 10
1 4 1

784

数据规模

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

对于所有测试点，保证 $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$，图中可能存在重边。

限制

时间限制：1.0 s

空间限制：512.0 MB