子图最短路

题目描述

给定包含 n 个结点 m 条边的带权无向图 G，结点依次以 1..n 编号。第 i 条边连接编号为 u[i] 与 v[i] 的两个结点，权值为 w[i]。 对于指定的区间 [l, r]，按以下方式构造图 G 的子图 G[l, r]：保留 G 中编号在区间 [l, r] 中的结点，删去其它编号不在 [l, r] 中的结点以及与之相连的边，剩余的结点和边构成子图 G[l, r]。 对于 G[l, r] 中的任意结点 i, j，记 d 为 i, j 在子图 G[l, r] 上的最短距离；若 i, j 在子图 G[l, r] 上不连通，则认为 d 为 1e9。 你需要求出所有区间 [l, r]（1 ≤ l ≤ r ≤ n）的 G[l, r] 内所有点对距离之和，对 1e9 取模的结果。

输入格式

第一行，两个正整数 n, m，表示结点数与边数。 接下来 m 行，第 i 行包含三个正整数 u[i], v[i], w[i]，表示一条连接 u[i] 与 v[i] 的权值为 w[i] 的边。

输出格式

输出一行，一个整数，表示答案对 1e9 取模的结果。

样例

输入

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

数据范围

保证 1 ≤ n ≤ 100，1 ≤ m ≤ 1000，1 ≤ u, v ≤ n，1 ≤ w ≤ 10000，图中可能存在重边。取模数为 1000000000。