#include <iostream>

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <queue>

#include <stack>

#include <algorithm>

#include <map>

#include <string>

typedef long long LL;

#define INF 0x3f3f3f3f

#define met(a, b) memset(a, b, sizeof(a))

#define N 200005

using namespace std;

struct node

{

    int v, w, Next;

}G[N*];

int n, m, c, dist[N], vis[N], l[N], v[N];

int Head[N], cnt;

void Add(int u, int v, int w)

{

    G[cnt].v = v;

    G[cnt].w = w;

    G[cnt].Next = Head[u];

    Head[u] = cnt++;

}

int spfa()

{

    for(int i=; i<=n*+; i++)

        dist[i] = INF;

    met(vis, );

    queue<int>Q;

    Q.push();

    vis[] = ;

    dist[] = ;

    while(!Q.empty())

    {

        int p = Q.front();Q.pop();

        vis[p] = ;

        for(int i=Head[p]; i!=-; i=G[i].Next)

        {

            int q = G[i].v;

            if(dist[q] > dist[p]+G[i].w)

            {

                dist[q] = dist[p]+G[i].w;

                if(!vis[q])

                {

                    vis[q] = ;

                    Q.push(q);

                }

            }

        }

    }

    return dist[n];

}

int main()

{

    int T, t = ;

    scanf("%d", &T);

    while(T--)

    {

        met(Head, -);

        met(v, );

        cnt = ;

        scanf("%d %d %d", &n, &m, &c);

        for(int i=; i<=n; i++)

        {

            scanf("%d", &l[i]);

            v[l[i]] = ;

        }

        for(int i=; i<n; i++)

        {

            if(v[i] && v[i+])

            {

                Add(n+i, n+i+, c);///层与层之间连边；

                Add(n+i+, n+i, c);

            }

        }

        for(int i=; i<=n; i++)

        {

            Add(n+l[i], i, );///当前点与它所在的层连边，边为0；

            if(l[i]!=) Add(i, n+l[i]-, c);///点和层间进行连边；

            if(l[i]!=n) Add(i, n+l[i]+, c);

        }

        for(int i=; i<=m; i++)

        {

            int u, v, w;

            scanf("%d %d %d", &u, &v, &w);

            Add(u, v, w);

            Add(v, u, w);

        }

        int ans = spfa();

        if(ans == INF) ans = -;

        printf("Case #%d: %d\n", t++, ans);

    }

    return ;

}