406044: GYM102222 F Moving On

Firdaws and Fatinah are living in a country with $$$n$$$ cities, numbered from $$$1$$$ to $$$n$$$. Each city has a risk of kidnapping or robbery.

Firdaws's home locates in the city $$$u$$$, and Fatinah's home locates in the city $$$v$$$. Now you are asked to find the shortest path from the city $$$u$$$ to the city $$$v$$$ that does not pass through any other city with the risk of kidnapping or robbery higher than $$$w$$$, a threshold given by Firdaws.

The input contains several test cases, and the first line is a positive integer $$$T$$$ indicating the number of test cases which is up to $$$50$$$.

For each test case, the first line contains two integers $$$n~(1\le n\le 200)$$$ which is the number of cities, and $$$q~(1\le q\le 2\times 10^4)$$$ which is the number of queries that will be given. The second line contains $$$n$$$ integers $$$r_1, r_2, \cdots, r_n$$$ indicating the risk of kidnapping or robbery in the city $$$1$$$ to $$$n$$$ respectively. Each of the following $$$n$$$ lines contains $$$n$$$ integers, the $$$j$$$-th one in the $$$i$$$-th line of which, denoted by $$$d_{i,j}$$$, is the distance from the city $$$i$$$ to the city $$$j$$$.

Each of the following $$$q$$$ lines gives an independent query with three integers $$$u, v$$$ and $$$w$$$, which are described as above.

We guarantee that $$$1\le r_i \le 10^5$$$, $$$1\le d_{i,j}\le 10^5~(i \neq j)$$$, $$$d_{i,i}=0$$$ and $$$d_{i,j}=d_{j,i}$$$. Besides, each query satisfies $$$1\le u,v\le n$$$ and $$$1\le w\le 10^5$$$.

For each test case, output a line containing Case #x: at first, where x is the test case number starting from $$$1$$$. Each of the following $$$q$$$ lines contains an integer indicating the length of the shortest path of the corresponding query.

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

Case #1:
0
1
3
0
1
2