魔法少女伊莉雅 - Problem

Ich weiss nicht, was soll es bedeuten,

Dass ich so traurig bin;

Ein Maerchen aus alten Zeiten,

Das kommt mir nicht aus dem Sinn.

士郎中了可爱的魔法少女伊莉雅苏菲尔·冯·爱因兹贝伦的魔眼之后，被带

回了伊莉雅的城堡。伊莉雅旋即“离开”去捉 Rin和Saber，但机智的士郎知道

Rin和 Saber 已经来到城堡救他，而走的伊莉雅只不过是替身。

然而，为了攒足 Saber 的好感度防止某日在麻婆神父面前被杀死，士郎决定

“逃出”爱因兹贝伦城堡。

由于 Archer 正在向城堡赶来，士郎决定尽可能拖延时间以防独自面对

Berserker的袭击。

不过，Servant 的感知和思考都是敏锐的，因此士郎如果绕了太远路，会被

Saber 发现而反而减少好感度，所以士郎决定走在比最短路长的所有路径中最短

的一条路径。当然， Rin 的感知也是很敏锐的，所以士郎如果走到了已经走到过的某个点，

那么就立刻会被 Rin 发现而以归还十年份魔力的宝石作为对 Saber 的保密条件

哦。本来故事这样就结束了，可是还有默默围观的伊莉雅。伊莉雅比 Saber 和

Rin想得多些【雾】，如果一条边(u, v, w)可能出现在最短路径上，顺序是 u→v （所

有边权为正），那么士郎如果沿 v→u 走了这条边，会立刻被伊莉雅发现而被做成

人偶哦~☆

不妨设伊莉雅的房间（士郎所在位置）为1号点，城堡大厅为n号点。很显

然，伊莉雅没有远坂间桐樱一样在居所设置机关（参见某BE 的道场）的兴趣，

因此每条边都是双向边。

第一行两个正整数n, m，分别表示点数和边数。

接下来 m 行每行三个正整数 u, v, w，表示点 u 与点 v 之间有一条权值为 w

的边。

第一行一个整数，表示所求路径的长度，若不存在则输出-1。

2 2
1 2 1
1 2 2

对于100%的数据，n ≤ 100000，m ≤ 500000，w ≤ 1000。

黑暗爆炸OJ