9538: 小塔的梦境迷宫

众所周知，小塔是一个爱做梦的孩子。这一天她梦见自己被巫师关进了一个迷宫之中，这个迷宫有$n$个房间，通过$m$条单向道路连接，迷宫的起点是1号房间，终点是$n$ 号房间。每条道路都有一个守路人，需要支付对应数量的金币才能通过，巫师告诉了小塔迷宫的起点和终点是哪个房间，并告诉小塔这个迷宫还存在着两个神秘的规则：

1.只有当走到终点时经过的路的数量是3的倍数时她才能顺利逃离迷宫。

2.每个房间都有一个类别属性，她可以花费$x$个金币在相同类别的属性之间瞬移（注意每次瞬移也算作走过了一条路），特殊地她可以在同个房间内进行瞬移

由于小塔在梦中时智商受到了极大的限制，所以她来求助你帮她算算走出迷宫最少需要花多少金币？（如果怎样都不能走出迷宫的话输出“-1”（不包含引号）即可）

第一行有一个整数，$T(1\le T\le 30)$，代表数据组数

每组数据第一行有三个整数，$n,m,x$，（2≤n≤105,2≤m≤106,1≤x≤1072≤n≤105,2≤m≤106,1≤x≤107)代表有$n$个房间，$m$条单向道路以及在同一类别的房间瞬移需要花费$x$个金币。

第二行有 $n$ 个整数 A1,A2,A3,⋯AnA1,A2,A3,⋯An , （1≤Ai≤n1≤Ai≤n）代表每个房间的种类。

接下来有$m$行，每行有三个整数ui,vi,diui,vi,di （ 1≤ui,vi≤n,ui≠vi,1≤di≤1071≤ui,vi≤n,ui=vi,1≤di≤107） ，代表一条从uiui到vivi的单项道路，需要花费didi点金币就能通过。保证不存在重边和自环。

数据保证∑n≤3⋅105,∑m≤106∑n≤3⋅105,∑m≤106