在一个奇幻王国里，有 个城市（编号依次为 到 ）和 条双向道路，第 条道路连接城市 和 ，基础通行时间为正整数 。此外，王国中每个城市都存在 个中枢魔法石，每个魔法石有一个能量值，非负能量值的魔法石称之为「坏魔法石」，负数能量值的魔法石称之为「好魔法石」，坏魔法石会增加通行所需时间，好魔法石会减少通行所需时间（增加和减少的时间即为能量值的多少），如果好魔法石足够强力，甚至可以实现时间倒流。 坏魔法石将会强制生效，导致基础通行时间增加，无法被控制。 好魔法石可以控制，选择是否生效，但使用好魔法石的总次数存在限制，第 次使用好魔法石生效以后，之后将无法利用任何城市的好魔法石来减少通行时间。换句话说，单次行程中好魔法石总使用次数不超过 次。 魔法石不会消失，可以多次使用。 当你从城市 前往城市 时，路径的实际通行时间计算如下： 通行时间 = 城市 到城市 的道路基础通行时间加上城市 生效的魔法石能量值。 请计算从城市 到城市 的最小实际通行时间，注意，您可以重复经过城市和道路。特别地，如果无论如何都无法到达城市 ，直接输出 。

输入描述:

第一行输入三个整数 。第二行输入 个整数 ，其中 表示第 个城市的魔法石能量。接下来 行，第 行输入三个整数 ，表示城市 与城市 之间存在一条通行时间为 的路径。除此之外，保证任意两个城市间至多存在一条道路。注意，本题不保证图的连通性，即可能存在两个城市无法通过任何路径互相到达的情况。

输出描述:

如果无论如何都无法到达城市 ，直接输出 ，否则输出一个整数，表示从城市 到城市 的最小实际通行时间。