给出了一个加权的无方向图，检查在顶点1和n之间是否存在权重k的路径。

看起来像一个NP问题，但要求我在2秒内检查它，K为

N和M非常小（

  

一个国家有n个城市，城市的编号是1到n，所有道路都指向。每条道路连接两个城市。

     

沃克先生真的很喜欢散步。沿任何方向向任何方向行驶都需要w（i）分钟。沃克先生并没有待在城市，一到达一个城市，他便立即去另一个城市。

     

Walker先生从排名第一的城市开始，希望在整整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个城市，则不可能。