4608：[GESP202603八级] 子图最短路
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：0
解决：0
题目描述
## 题目背景
2026 年 03 月 GESP C++ 八级编程第 2 题
## 题目描述
给定包含 $n$ 个结点 $m$ 条边的**带权无向图** $G$，结点依次以 $1, 2, ..., 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$ 取模的结果。
## 样例
```input1
3 2
1 2 1
2 3 2
```
```output1
9
```
```input2
4 6
1 2 100
2 3 100
3 4 100
1 3 10
2 4 10
1 4 1
```
```output2
784
```
## 数据范围
对于 $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$。图中可能存在重边。