⼦图最短路

题目描述

给定包含 个结点 条边的带权⽆向图 ，结点依次以 编号。第 （ ）条边连接编号为 与 的两个结点，权值为 。 对于指定的 ，按以下⽅式构造图 的⼦图 ： 保留 中编号在区间 中的结点。删去其它编号不在 中的结点以及与之相连的边。剩余的结点和边构 成⼦图 。 对于 中的任意结点 应有 。记 在⼦图 上的最短距离为 。特殊地，若 在⼦图 上不连通，则认为 。 你需要求出 对 取模的结果。 题⽬中的英⽂字母 使⽤了特殊写法 ，以避免英⽂字母 与数字 混淆。

输入格式

第⼀⾏，两个正整数 ，表⽰结点数与边数。 接下来 ⾏，第 （ ）⾏包含三个正整数 ，表⽰⼀条连接结点 的权值为 的边。

输出格式

输出⼀⾏，⼀个整数，表⽰ 对 取模的结果。

样例输入 #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

数据范围

对于 的测试点，保证 。 对于所有测试点，保证 ， ， ， 。图中可能存在重边。

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度等级：⭐⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。