#include<iostream>

#include<cstring>

#include<stdio.h>

#include<vector>

#include<string>

#include<algorithm>

#include<queue>

#include<cmath>

using namespace std;

typedef long long LL;

const int maxn = 3e5+;

const LL INF = 1ll<<;

struct Edge{

    int to,next;

    LL val;

};

struct HeapNode{

    LL d;           //费用或路径

    int u;

    bool operator < (const HeapNode & rhs) const{return d > rhs.d;}

};

struct Dijstra{

    int n,m,tot;

    Edge edges[maxn<<];

    bool used[maxn];

    LL d[maxn];

    int head[maxn];

    void init(int n){

        this->n = n;

        this->tot=;

        memset(head,-,sizeof(head));

    }

    void Addedge(int u,int v ,LL dist){

        edges[tot].to = v;

        edges[tot].val = dist;

        edges[tot].next = head[u];

        head[u] = tot++;

    }

    void dijkstra(int s){

        memset(used,,sizeof(used));

        priority_queue<HeapNode> Q;

        for(int i=;i<=n;++i)    d[i]=INF;

        d[s]=;

        Q.push((HeapNode){,s});

        while(!Q.empty()){

            HeapNode x =Q.top();Q.pop();

            int u =x.u;

            if(used[u])

                continue;

            used[u]= true;

            for(int i=head[u];~i;i=edges[i].next){

                Edge & e = edges[i];

                if(d[e.to] > d[u] + e.val){

                    d[e.to] = d[u] +e.val;

                    Q.push((HeapNode){d[e.to],e.to});

                }

            }

        }

    }

}G;

int lay[maxn];

//#define LOCAL

int main()

{

    #ifdef LOCAL

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

       #endif

    int N,M,T,u,v,cas=;

    LL tmp,C;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d%lld",&N,&M,&C);

        G.init(*N);

        for(int i=;i<=N;++i){

            scanf("%d",&tmp);

            G.Addedge(i,tmp+N,);           //1~N为层,N~2*N为出点，2*N~3*N为入点

            G.Addedge(tmp+*N,i,);

        }

        for(int i=;i<=N-;++i){

            G.Addedge(N+i,*N+i+,C);       //将相邻两层出点入点对应连接

            G.Addedge(N+i+,*N+i,C);

        }

        for(int i=;i<=M;++i){

            scanf("%d%d%lld",&u,&v,&tmp);

            G.Addedge(u,v,tmp);

            G.Addedge(v,u,tmp);

        }

        G.dijkstra();

        if(G.d[N]==INF) G.d[N]=-;

        printf("Case #%d: %lld\n",cas++,G.d[N]);

    }

    return ;

}