最短路径

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

为了准备一年一度的校赛,大家都在忙着往赛场搬运东西,比如气球什么的。这时 YY 也没有闲着,他也加入了搬运工的行列。已知学校有 N 个路口和 M 条路,YY 并不是把东西直接搬到赛场,而是从 S 路口搬运到 T 路口。由于 YY 非常懒而且他有轻度强迫症。所以他要走的路需要尽可能的短,并且走路径 X 的倍数。

Input

 

输入的第一行为一个正整数T(1 T 20),代表测试数据组数。

对于每组测试数据:

输入的第一行为两个正整数 N M1 N 100, 1 M 10000)。

接下来M行每行三个正整数 UVW0 U, V < N, 0 W 230 ),代表有一条从UV的长度为W有向路径

最后一行为三个正整数ST X0 S, T < N, 1 X 10)。

Output

 

对于每组测试数据,输出满足条件的从 S T 的最短路径。如果从 S T 不可达,或者无法满足路径数是 X 的倍数,输出No Answer!”(不包含引号)

注意:64-bit 整型请使用 long long 来定义,并且使用 %lld cincout 来输入输出,请不要使用 __int64 %I64d

Sample Input

2
2 1
0 1 1
0 1 2
3 2
0 1 1
1 2 1
0 2 2

Sample Output

No Answer!
2

Hint

 

Source

“师创杯”山东理工大学第五届ACM程序设计竞赛