Background

Related multiple-choice and true/false questions: https://ti.luogu.com.cn/problemset/1212.

Problem Description

Given a weighted undirected graph $G$ with $n$ nodes and $m$ edges, the nodes are numbered $1, 2, \dots, n$ in order. The $i$-th edge ($1 \le i \le m$) connects two nodes numbered $u_i$ and $v_i$, with weight $w_i$.

For given $1 \le \ell \le r \le n$, construct a subgraph $G(\ell, r)$ of $G$ as follows:

• Keep the nodes in $G$ whose numbers are in the interval $[\ell, r]$. Delete all other nodes whose numbers are not in $[\ell, r]$ and the edges incident to them. The remaining nodes and edges form the subgraph $G(\ell, r)$.

For any nodes $u, v$ in $G(\ell, r)$, we have $\ell \le u, v \le r$. Let the shortest distance between $u$ and $v$ in the subgraph $G(\ell, r)$ be $d(\ell, r, u, v)$. In particular, if $u$ and $v$ are not connected in $G(\ell, r)$, then define $d(\ell, r, u, v) = 0$.

You need to compute $\sum_{\ell=1}^{n} \sum_{r=\ell}^{n} \sum_{u=\ell}^{r} \sum_{v=u}^{r} d(\ell, r, u, v)$ modulo $10^9$.

• In this problem, the English letter $l$ is written as $\ell$ to avoid confusion between the letter $l$ and the digit $1$.

Input Format

The first line contains two positive integers $n, m$, representing the number of nodes and the number of edges.

The next $m$ lines: the $i$-th line ($1 \le i \le m$) contains three positive integers $u_i, v_i, w_i$, representing an edge connecting nodes $u_i$ and $v_i$ with weight $w_i$.

Output Format

Output one line with one integer, representing $\sum_{\ell=1}^{n} \sum_{r=\ell}^{n} \sum_{u=\ell}^{r} \sum_{v=u}^{r} d(\ell, r, u, v)$ modulo $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

Hint

For $40\%$ of the testdata, it is guaranteed that $2 \le n \le 20$.

For all testdata, it is guaranteed that $2 \le n \le 100$, $2 \le m \le \frac{n(n-1)}{2}$, $1 \le u_i, v_i \le n$, and $1 \le w_i \le 10^6$. There may be multiple edges in the graph.

Translated by ChatGPT 5