// #pragma GCC optimize("-std=c++14")

#include <bits/stdc++.h>

using namespace std;

// #define int long long
// #define x first
// #define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);

typedef long long LL;
typedef pair<int, int> PII;

const int N = 200010;
const int INF = 0x3f3f3f3f;

template<typename Type>
inline void read(Type &res)
{
    res = 0;
    int ch = getchar(), flag = 0;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }

int n, m, k, val[N];
int h[N], e[N << 1], ne[N << 1], w[N << 1], idx;
int rest[N], hh = 0, tt = -1;
array<int, 3> que[N];

inline void add(int a, int b, int c) { e[++ idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx; }

signed main()
{
    memset(h, -1, sizeof h), idx = -1;
    read(n, m, k);
    for (int ver = 1; ver <= n; ver ++) read(val[ver]);
    while (m --)
    {
        int a, b, c; read(a, b, c);
        add(a, b, c), add(b, a, c);
    }

    que[++ tt] = {1, k, 0};
    while (hh <= tt)
    {
        // auto [ver, hp, dist] = que[hh ++];
        int ver = que[hh][0], hp = que[hh][1], dist = que[hh ++][2];
        if (ver == n) return cout << dist << '\n', 0;
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int to = e[i];
            if (hp <= w[i]) continue;
            int minn = min(k, hp - w[i] + val[to]);
            if (rest[to] >= minn) continue;
            que[++ tt] = {to, minn, dist + 1};
            rest[to] = minn;
        }
    }

    return 0;
}