6112 - GESP:2026-3月等级8-T2-子图最短路
Time Limit : 1 秒
Memory Limit : 512 MB
给定包含 n个结点m 条边的带权无向图G ，结点依次以1,2...n 编号。第 i（1<=i<=m ）条边连接编号为ui 与vi的两个结点，权值为wi 。
对于指定的1<=l<=r<=n ，按以下方式构造图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)=0 。
你需要求出
Input
第一行，两个正整数n,m ，表示结点数与边数。 接下来m 行，第i（1<=i<=m ）行包含三个正整数ui,vi,wi ，表示一条连接结点ui,vi 的权值为wi 的边。
Output
Examples
Input
3 2 1 2 1 2 3 2
Output
9
Input
4 6 1 2 100 2 3 100 3 4 100 1 3 10 2 4 10 1 4 1
Output
784
Hint
数据范围
对于40% 的测试点，保证2<=n<=20 。
对于所有测试点，保证2<=n<=100 ，2<=m<=n *（n-）/2 ，1<=UI,VI<=N,1<=WI<=10^6 。图中可能存在重边。