A67850. 子图最短路

试题名称：子图最短路 

时间限制：1.0 s 

内存限制：512.0 MB 

3.2.1 题目描述 

给定包含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。 

你需要求出d(e,r,u,v)对10⁹取模的结果。 

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

3.2.2 输入格式 

第一行，两个正整数n,m，表示结点数与边数。 

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

3.2.3 输出格式 

输出一行，一个整数，表示d(e,r,u,v)对10⁹取模的结果。

3.2.4 样例 

3.2.4.1 输入样例 1 

3.2.4.2 输出样例 1 

3.2.4.3 输入样例 2

3.2.4.4 输出样例 2 

3.2.5 数据范围 

对于40%的测试点，保证2≤n≤20。 

对于所有测试点，保证2≤n≤100，2≤m≤，1≤u_i,v_i≤n，1≤w_i≤10⁶ 。图中可能存在重边。