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