大体上就是有n个点，n个层，每层上存在一些点，任意一层上的点都可以通过消费c到达另一个层上任一点，然后最有还有m条的额外的双向边可联通。其中需要知道的就是，同一个层上的点不能直接到达，也就是说，在同一个层并不代表到达目的地了，所以我的想法就是，n个层和n个点都当作点，建一个总量为2*n的图，每层与层上的点建一个层向点的单向边，如果相邻层都有点，那么建一条两层之间的双向边，然后对点来说，分别建一条相邻层和他的双向边（放心建，就算建到空层上没有层之间的边也回不来），最后跑一边spfa就好了。

#include<iostream>
#include<cstdio>
#include<queue>
#include<functional>
#include<vector>
using namespace std;
struct ***
{
	int to, len;
	***(int a, int b) : to(a), len(b) {}
	bool operator <(const *** &a)const
	{
		return len > a.len;
	}
};
struct ***er
{
	int to, len, ne;
}lay[800005];
int n, m, c, cnt;
vector<***>layer[300005];
bool vis[300005];
int loca[300005];
int head[300005];
int d[300005];
void add(int from, int to, int len)
{
	lay[cnt].to = to;
	lay[cnt].len = len;
	lay[cnt].ne = head[from];
	head[from] = cnt++;
}
void init()
{
	memset(vis, 0, sizeof(vis));
	for (int s = 0; s <= 2*n; s++)
	{
		head[s] = -1;
		layer[s].clear();
		d[s] = 0x3f3f3f3f;
	}
	cnt = 0;
}
void spfa()
{
	priority_queue<***>q;
	vis[1+n] = 1;
	q.push(***{ n+1,0 });
	d[1+n] = 0;
//	cout << loca[1] << endl;
	while (!q.empty())
	{
		int t = q.top().to;
		q.pop();	
		vis[t] = 0;
		for (int s = head[t]; ~s; s = lay[s].ne)
		{
			//	cout << t << " " << lay[s].to << " " << lay[s].len << endl;
			if (d[lay[s].to] > d[t] + lay[s].len)
			{	

				d[lay[s].to] = d[t] + lay[s].len;
				if (!vis[lay[s].to])
				{
					q.push(***{ lay[s].to , d[lay[s].to] });
					vis[lay[s].to] = 1;
				}
			}
		}
	}
}
int main()
{
	int te, cas = 1;
	scanf("%d", &te);
	while (te--)
	{	
		scanf("%d%d%d", &n, &m, &c);
		init();
		int a, b;
		for (int s = 1; s <= n; s++)
		{
			scanf("%d", &a);
			layer[a].push_back(***{s,0});
			loca[s] = a;
		}
		for (int s = 1; s <= n; s++)//点与层
		{
			add(loca[s], s + n, 0);
			if (loca[s] > 1)
			{
				add(n + s, loca[s] - 1, c);
			}
			if (loca[s] < n)
			{
				add(n + s, loca[s] +1, c);
				//cout << s << " " << loca[a] + 1 << endl;
			}
		}
		for (int s = 1; s < n; s++)//层与层；
		{
			if (layer[s].size() && layer[s + 1].size())
			{
				add(s, s + 1, c);
				add(s + 1, s, c);
			}
		}
		while (m--)
		{
			scanf("%d%d%d", &a, &b, &c);//额外边；
			add(a+n, b+n, c);
			add(b+n, a+n, c);
		}
		spfa();
		if (d[n+n] == 0x3f3f3f3f)
		{
			d[n+n] = -1;
		}
		printf("Case #%d: %d\n", cas++, d[n+n]);
	}
	return 0;
}