给定包含 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) 中的任意结点 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 取模的结果。
第一行，两个正整数 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 取模的结果。
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 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。图中可能存在重边。