o60_oct_c1_collecting

#include <bits/stdc++.h>
using namespace std;
const int N = 50010;
using pi = pair <int, int>;
using pii = pair <int, pi>;
const int INF = 2e9;
vector <pi> g[N];
int dis[N][40];
bool visited[N][40];
int level[N];
int main(){

    for(int i=0;i<=50000;i++){
        for(int j=0;j<=30;j++){
            dis[i][j] = INF;
            visited[i][j] = false;
        }
    }

    int n, m, L;
    scanf("%d%d%d", &n, &m, &L);
    int s, t;
    scanf("%d%d", &s, &t);
    for(int i=1;i<=n;i++){
        scanf("%d", &level[i]);
    }
    for(int i=1;i<=m;i++){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({v, w});
    }
    priority_queue <pii, vector <pii>, greater <pii>> pq;
    pq.push({0, {s, 0}});
    while(!pq.empty()){
        int d = pq.top().first;
        int u = pq.top().second.first;
        int l = pq.top().second.second;
        pq.pop();
        if(visited[u][l])
            continue;
        visited[u][l] = true;
        if(l == L and u == t) {
            printf("%d", d);
            return 0;
        }
        for(auto vw: g[u]){
            int v = vw.first;
            int w = vw.second;
            if(level[v] == l+1 and !visited[v][l+1] and d + w < dis[v][l+1]){
                dis[v][l+1] = d + w;
                pq.push({d+w, {v, l+1}});
            }
            else if(!visited[v][l] and d + w < dis[v][l]){
                dis[v][l] = d + w;
                pq.push({d+w, {v, l}});
            }
        }
    }
    printf("-1");
    return 0;
}