#include <bits/extc++.h>
#pragma GCC optimize(3, "Ofast", "inline")
#define endl '\n'
typedef long long ll;
#define int ll
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

constexpr int inf = 0x3f3f3f3f3f3f3f3fll, lmt = 2e5;

vector<pair<int, int>> ve[lmt + 10];
vector<int> g[lmt + 10];
int id[lmt + 10], dis[lmt + 10][3];
__gnu_pbds::priority_queue<pair<int, pair<int, int>>, greater<>, thin_heap_tag> q;

void Main() {
  int n, m, x;
  cin >> n >> m >> x;
  while (q.size())
    q.pop();
  for (int i = 1; i <= n; ++i) {
    ve[i].clear();
    dis[i][0] = dis[i][1] = dis[i][2] = inf;
    g[i].clear();
  }
  for (int i = 1; i <= n; ++i) {
    int a;
    cin >> a;
    id[i] = a;
    g[a].push_back(i);
  }
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    ve[u].emplace_back(v, w);
  }
  q.push({0, {0, 1}});
  dis[1][0] = 0;
  while (q.size()) {
    const auto &[cost, _] = q.top();
    const auto &[len, pos] = _;
    q.pop();
    if (pos == n && len == 0) {
      cout << cost << endl;
      return;
    }
    for (auto &ed: ve[pos]) {
      int v = ed.first, w = ed.second, ne = (len + 1) % 3;
      if (cost + w < dis[v][ne]) {
        dis[v][ne] = cost + w;
        q.push({dis[v][ne], {ne, v}});
      }
    }
    for (int v: g[id[pos]]) {
      int ne = (len + 1) % 3;
      if (cost + x < dis[v][ne]) {
        dis[v][ne] = cost + x;
        q.push({dis[v][ne], {ne, v}});
      }
    }
  }
  cout << -1 << endl;
}

#define __CP_MULTI_TEST_CASES

signed main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int t = 1;
#ifdef __CP_MULTI_TEST_CASES
  cin >> t;
#endif
  while (t--) {
    Main();
  }
  return 0;
}