#P4283. 魔法少女伊莉雅
魔法少女伊莉雅
魔法少女伊莉雅
题目描述
士郎想从爱因兹贝伦城堡的房间 走到大厅 。城堡的通道是带正权的无向边。他不想走最短路,但希望在所有合法且严格比最短路长的路径中,选一条长度最小的。
合法路径不能经过重复的顶点。若某一条边能在某条从 到 的最短路上沿 经过,士郎就不能沿 走这一条边。这个限制针对具体的边,存在重边时分别判断。最短路长度按原无向图计算。
输入格式
第一行两个整数 ,表示顶点数和边数。接下来 行,每行三个整数 ,表示一条连接 、长度为 的双向通道。
输出格式
输出一行一个整数,表示目标路径的最小长度。若不存在这样的路径,输出 -1。
样例 #1
样例输入 #1
2 2
1 2 1
1 2 2
样例输出 #1
2
样例说明
两条平行通道的长度分别为 和 ,最短路长度为 ,所以选长度为 的通道。
样例 #2
3 3
1 2 5
1 3 1
2 3 8
13
最短路是 ,长度为 ;合法较长简单路径是 ,长度为 。绕回已经经过的节点不合法。
数据规模与约定
,,,。