题目描述

给定包含n个结点m条边的带权无向图G，结点依次以1,2,…,n编号。第i（1≤i≤m）条边连接编号为$u_i$与$v_i$的两个结点，权值为$w_i$。

对于指定的1≤e≤r≤n，按以下方式构造图G的子图G(e,r)：保留G中编号在区间$[e,r]$中的结点，删去其它编号不在$[e,r]$中的结点以及与之相连的边，剩余的结点和边构成子图G(e,r)。

对于G(e,r)中的任意结点u,v应有$e≤u,v≤r$。记u,v在子图G(e,r)上的最短距离为$d(e,r,u,v)$。特殊地，若u,v在子图G(e,r)上不连通，则认为$d(e,r,u,v)=0$。

你需要求出下式对$10^9$取模的结果： $$\sum{e=1}^{n}\sum{r=e}^{n}\sum{u=e}^{r}\sum{v=u}^{r} d(e,r,u,v)$$

注：题目中的英文字母l使用了特殊写法e，以避免英文字母l与数字1混淆。

输入格式

第一行，两个正整数n,m，表示结点数与边数。 接下来m行，第i（1≤i≤m）行包含三个正整数$u_i,v_i,w_i$，表示一条连接结点$u_i$、$v_i$的权值为$w_i$的边。

输出格式

输出一行，一个整数，表示上述求和结果对$10^9$取模的结果。

样例

样例1输入

3 2
1 2 1
2 3 2

样例1输出

9

样例2输入

4 6
1 2 100
2 3 100
3 4 100
1 3 10
2 4 10
1 4 1

样例2输出

784

数据范围

• 对于40%的测试点，保证$2≤n≤20$。
• 对于所有测试点，保证$2≤n≤100$，$2≤m≤\frac{n(n-1)}{2}$，$1≤u_i,v_i≤n$，$1≤w_i≤10^6$。图中可能存在重边。

限制条件

• 时间限制：1.0 s
• 内存限制：512.0 MB