给出了一个加权的无方向图，检查在顶点1和n之间是否存在权重k的路径。
看起来像一个NP问题，但要求我在2秒内检查它，K为<= 10 ^ 18。我们可以根据需要使用每条道路多次。将不胜感激。
N和M非常小（<= 50），因此我考虑将dp用于权重最大为k的路径。N，M，K是整数，边缘的权重<10 ^ 4。该图可能未连接。很遗憾，此问题来自代码部队培训，该语句不是英语，因此在附加该语句时不会有任何用处。
有一个国家有n个城市，城市的编号从1到n，所有道路均通向。每条道路连接两个城市。
沃克先生真的很喜欢散步。沿任何方向向任何方向行驶都需要w（i）分钟。沃克先生不住在城市，一到达一个城市，他便立即去另一个城市。
沃克先生从排名第一的城市开始，希望在整整K分钟内到达第n个城市。您需要检查是否可行。
输入-第一行包含两个整数n，m（1 ??? n，？m ??? 50）。接下来的m行描述道路a（i）-起点，b（i）-终点，d（i）-沿着这条路行驶所需的时间（1 ??? ai，？bi ??? n; 1 ??? di ??? 10 ^ 4）。
最后一行包含数字k-沃克先生希望其路径采用的时间（1 ??? t ??? 10 ^ 18）。
如果可以的话，打印是可能的；如果沃克先生不能在准确的k分钟内到达第n个城市，则不可能。