lqp18_31 和 1tthinking 经常出题来虐 ftiasch。
有一天，lqp18_31 搞了一个有向图，每条边的长度都是 。他想让 ftiasch 求出点 到点 的最短路。"水题啊。"，ftiasch 这么说道。
所以 1tthinking 把某些边的长度增加了 （也就是说，每条边的长度不是 就是 ）。现在，可怜的 ftiasch 要向你求助了。
第一行两个整数 表示点和边的数量。
接下来 行每行三个整数 ，表示一条从 到 ，边权是 的有向边。
一个整数，表示点 到点 的最短路。数据保证至少存在一条路径。
3 3 1 2 1 2 3 1 1 3 2
2
对于 的数据，，，。
