题号：NC50807
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
题目描述
大中锋正在一个游乐场里玩耍。游乐场里有很多娱乐设施，娱乐设施之间相互有道路相连，经过每一条路都需要花费一定的时间。为了方便游客，每一个娱乐设施旁都会配有一个小卖部，一部分小卖部会销售可乐，另一部分会销售汉堡。
由于大中锋十分贪吃，所以每当他走到一个娱乐设施，他都会先去购买一杯可乐或一个汉堡，并把它们吃掉。但如果大中锋吃掉的汉堡数量比他喝掉的可乐数量多于k，那他就会感到很渴；如果喝掉的可乐数量比吃掉的汉堡数量多于k，那他就会感到很饿。
现在大中锋正在第a个娱乐设施，他想前往第b个娱乐设施，但在他前进的路途中他不希望自己很渴或很饿。大中锋想知道自己在路上最少花费多少时间。但由于大中锋很懒惰，他不想思考这个问题。你能帮助他解决这个问题吗？
注意：大中锋非常贪吃，所以他到达每个点的第一件事是去吃（或者喝），才考虑其他的事情，所以在起始点和终点他都会去买汉堡（可乐），你也需要保证在这两个点他不会感到很饿或者很渴。
由于大中锋十分贪吃，所以每当他走到一个娱乐设施，他都会先去购买一杯可乐或一个汉堡，并把它们吃掉。但如果大中锋吃掉的汉堡数量比他喝掉的可乐数量多于k，那他就会感到很渴；如果喝掉的可乐数量比吃掉的汉堡数量多于k，那他就会感到很饿。
现在大中锋正在第a个娱乐设施，他想前往第b个娱乐设施，但在他前进的路途中他不希望自己很渴或很饿。大中锋想知道自己在路上最少花费多少时间。但由于大中锋很懒惰，他不想思考这个问题。你能帮助他解决这个问题吗？
注意：大中锋非常贪吃，所以他到达每个点的第一件事是去吃（或者喝），才考虑其他的事情，所以在起始点和终点他都会去买汉堡（可乐），你也需要保证在这两个点他不会感到很饿或者很渴。
输入描述:
多样例输入，第一行输入一个正整数T表示样例数。
对于每一个样例：
第一行三个数字n,m,k，n代表游乐场一共有多少个娱乐设施，m代表游乐场一共有多少条道路，k的意义如题面中所述。
接下来有一行n个数字，第i个数字代表第i个小卖部销售的是什么，1代表可乐，2代表汉堡。
接下来有m行输入，每行三个数字p,q,t，代表从第p个娱乐设施到第q个娱乐设施有一条道路，通过这条道路需要花费t单位时间。最后一行有两个整数a,b，代表大中锋想从娱乐设施a前往娱乐设施b。
输出描述:
每一组样例输出一行整数t，代表大中锋在路上既不会感到很渴也不会感到很饿的情况下，从娱乐设施a到娱乐设施b花费的最少时间，如果无法达到，输出-1。
备注:
对于的数据，n≤50,m≤1000；
对于的数据，n≤10000,m≤100000,k≤10,t≤10000。
对于所有数据，保证T≤10，且每个样例点的大数据不超过2个。