#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int INF = 1e9;
const int MAXN = 100000;
const int MAXM = 500000;

struct Edge {
    int to, cost;
};

vector<Edge> G[MAXN + 1], G_rev[MAXN + 1];  // 原图和反图的邻接表
int price[MAXN + 1];
int D[MAXN + 1], F[MAXN + 1];  // D表示从1号城市到其他城市的最小价格，F表示从n号城市到其他城市的最大价格
bool vis[MAXN + 1];  // 标记数组

void Dijkstra(int start, vector<Edge> G[], int dist[], bool isMin) {
    //priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pq;
    memset(vis, false, sizeof(vis));
    fill(dist, dist + MAXN + 1, isMin ? INF : 0);
    dist[start] = price[start];
    pq.push({ price[start], start });

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;

        for (Edge e : G[u]) {
            int v = e.to;
            if (isMin) {  // 最小值更新
                if (dist[v] > min(dist[u], price[v])) {
                    dist[v] = min(dist[u], price[v]);
                    pq.push({ dist[v], v });
                }
            }
            else {  // 最大值更新
                if (dist[v] < max(dist[u], price[v])) {
                    dist[v] = max(dist[u], price[v]);
                    pq.push({ dist[v], v });
                }
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        cin >> price[i];
    }

    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        G[x].push_back({ y, 0 });  // 原图
        G_rev[y].push_back({ x, 0 });  // 反图
        if (z == 2) {  // 双向道路，添加反向边
            G[y].push_back({ x, 0 });
            G_rev[x].push_back({ y, 0 });
        }
    }

    Dijkstra(1, G, D, true);  // 从1号城市出发，计算最小价格
    Dijkstra(n, G_rev, F, false);  // 从n号城市出发（反图），计算最大价格

    int maxProfit = 0;
    for (int i = 1; i <= n; ++i) {
        if (F[i] > D[i]) {
            maxProfit = max(maxProfit, F[i] - D[i]);
        }
    }

    cout << maxProfit << endl;
    return 0;
}