直接建图利用最短路算法去搞。
这里首先说一下最短路的几种算法以及各自的用途：
迪杰斯特拉算法：求单源最短路的算法，要求图中不能有负边，否则就破坏了这个算法的贪心策略。
SPFA：也是求单源最短路的算法，这个算法在图中有负边的时候可以用，一般如果图中没有负边不用，毕竟是将图中所有点都更新到最短的方式，时间复杂度较大。
弗洛伊德算法：求全部最短路的，如果要求两两之间的最短路用它。
那么这道题就是一个建边的问题了，要注意会出重复的边，要注意保留短边。 
//图论问题，通过不同层去建立不同层之间的连线，然后还有特殊连线。将图建立起来之后利用Dijkstra算法即可
//可以用hash去保存每个层里面的点编号，然后直接连线即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n, m, c;
//只用链式前向星存图
struct sy{
    int to;
    int next;
    int w;
} edge[maxn*10];
int head[maxn*10];
int cnt = 0;
struct Node {
    int number;
    int len;
    bool operator < (const Node& n) const
    {
        return len>n.len;
    }
};
priority_queue<Node> pq;
int ans[maxn];
int bianhao[maxn];
bool vis[maxn];
vector<int> mp[maxn];
map<pair<int, int>, int> mpr;

void add_edge(int x, int y, int w)
{
    edge[++cnt].next = head[x];
    edge[cnt].to = y;
    edge[cnt].w = w;
    head[x] = cnt;
}

void Dijkstra(int bg)
{
    memset(ans, 127, sizeof(ans));
    pq.push({bg, 0});
    ans[bg] = 0;
    while (pq.size())
    {
        int number = pq.top().number;
        pq.pop();
        if (vis[number]) continue;
//         cout<<"number="<<number<<endl;
        vis[number] = true;
        for (int i=head[number];i;i = edge[i].next)
        {
            int to = edge[i].to;
            int w = edge[i].w;
            if (ans[number]+w<ans[to])
            {
                ans[to] = ans[number]+w;
//                 cout<<"to="<<to<<" ans[to]="<<ans[to]<<endl;
                pq.push({to, ans[to]});
            }
        }
    }
    if (ans[n]>=2139062143) cout<<-1;
    else
        cout<<ans[n];
}

int main()
{
    int x, y, w;
    int l;
    cin>>n>>m>>c;
    for (int i=1;i<=n;i++)
    {
        cin>>l;
        mp[l].push_back(i);
        bianhao[i] = l;
    }
    //将层级之间连线
    for (int i=1;i<=n;i++)
    {
        int layer = bianhao[i];
        for (int j=0;j<mp[layer-1].size();j++)
        {
            mpr[{i,mp[layer-1][j]}] = c;
        }
        for (int j=0;j<mp[layer+1].size();j++)
        {
            mpr[{i, mp[layer+1][j]}] = c;
        }
    }
    //为额外的边建立
    for (int i=1;i<=m;i++)
    {
        cin>>x>>y>>w;
        if (mpr[{x,y}]!=0)
        {
            mpr[{x,y}] = min(mpr[{x,y}], w);
        }
        else
        {
            mpr[{x,y}] =  w;
        }
        if (mpr[{y,x}]!=0)
        {
            mpr[{y,x}] = min(mpr[{y,x}], w);
        }
        else
        {
            mpr[{y,x}] =  w;
        }
    }
    //遍历边开始建图
    map<pair<int, int>, int>::iterator it;
    for (it = mpr.begin();it!=mpr.end();it++)
    {
//         cout<<(*it).first.first<<' '<<(*it).first.second<<endl;
        add_edge((*it).first.first, (*it).first.second, (*it).second);
    }
    //开始迪杰斯特拉求最短路
    Dijkstra(1);
    
    return 0;
}