vector<pair<int,int> > g[N];
int a[N];
int f[N],n,m,C;

struct node
{
    int u,cost;

    node(){}
    node(int _u,int _cost)
    {
        u=_u;
        cost=_cost;
    }

    int operator<(const node &a) const
    {
        return cost>a.cost;
    }
};

int cal()
{
    priority_queue<node> Q;
    Q.push(node(1,0));
    int i;
    FOR1(i,n*3) f[i]=INF;
    f[1]=0;
    while(!Q.empty())
    {
        int u=Q.top().u;
        Q.pop();

        if(u==n) return f[u];

        FOR0(i,SZ(g[u]))
        {
            int v=g[u][i].first;
            int w=g[u][i].second;
            if(f[u]+w<f[v])
            {
                f[v]=f[u]+w;
                Q.push(node(v,f[v]));
            }
        }
    }
    return -1;
}

void add(int u,int v,int w)
{
    g[u].pb(MP(v,w));
}

int main()
{
    int num=0;
    rush()
    {
        RD(n,m,C);
        int i;
        FOR1(i,n*3) g[i].clear();
        FOR1(i,n-1)
        {
            add(n+i*2-1,n+(i+1)*2,C);
            add(n+(i+1)*2-1,n+i*2,C);
        }
        FOR1(i,n)
        {
            RD(a[i]);
            add(i,n+a[i]*2-1,0);
            add(n+a[i]*2,i,0);
        }
        FOR1(i,m)
        {
            int u,v,w;
            RD(u,v,w);
            add(u,v,w);
            add(v,u,w);
        }
        int ans=cal();
        printf("Case #%d: %d\n",++num,ans);
    }
}