python

from collections import deque

n, m = map(int, input().split())
prices = [0] + list(map(int, input().split()))  # 1-indexed

# 正向图和反向图
graph = [[] for _ in range(n + 1)]
rev_graph = [[] for _ in range(n + 1)]

for _ in range(m):
    x, y, z = map(int, input().split())
    if z == 1:  # 单向
        graph[x].append(y)
        rev_graph[y].append(x)
    else:  # 双向
        graph[x].append(y)
        graph[y].append(x)
        rev_graph[x].append(y)
        rev_graph[y].append(x)

# 正向：从1出发，记录到每个可达城市的最低买入价
min_price = [float('inf')] * (n + 1)
visited = [False] * (n + 1)
q = deque([1])
visited[1] = True
min_price[1] = prices[1]

while q:
    u = q.popleft()
    for v in graph[u]:
        new_min = min(min_price[u], prices[v])
        if not visited[v] or new_min < min_price[v]:
            visited[v] = True
            min_price[v] = new_min
            q.append(v)

# 反向：从n出发，标记能到达n的城市
can_reach_n = [False] * (n + 1)
q = deque([n])
can_reach_n[n] = True

while q:
    u = q.popleft()
    for v in rev_graph[u]:
        if not can_reach_n[v]:
            can_reach_n[v] = True
            q.append(v)

# 计算最大差价
ans = 0
for i in range(1, n + 1):
    if visited[i] and can_reach_n[i]:
        ans = max(ans, prices[i] - min_price[i])

print(ans)