'''
题目要求的答案是从1走到N的所有可能的路径上，靠后的最大值和靠前的最小值之间的差值的最大值，先用DP
的思维分析问题，所有路径方案可以用分割点k进行区分，表示买入发生在1到K的路径上, 卖出发生在K到N的
路径上，dp(k)表示从1到k所有可能路径上出现的最小值，dp(k) = min{dp(s1), dp(s2)....dp(sn), w[k]}
其中sx是能走到k的上一个点，w[k]是k这个点的权值，但是这个DP显然可能有环，常规的DP递推会死循环，
所以只能转成最短路来求解，1到x距离就定义为dp(x), dp(k) = min{dp(s1), dp(s2)....dp(sn), w[k]}
就是距离的计算公式，最多只有N个点，根据SPFA的思维，从起点走到K最多走N-1次，距离最小值一定得到了，同样的
把所有点反向，求N到所有点的最长路径，就可以得到任意一个点K走到N的所有经过节点中的最大值，正反两次
SPFA就可以求出任何一点K，从1走到K的节点最小值和K走到N的节点最大值，最后枚举所有的K，用对应的最大值
减去最小值，取其中最大的差值即可
'''
from collections import deque

n, m = map(int, input().split())
w = [0] + list(map(int, input().split()))

link = [[] for _ in range(n+1)]
link_rev = [[] for _ in range(n+1)]
for i in range(m):
    a, b, type = map(int, input().split())
    if type == 1:
        link[a].append(b)
        link_rev[b].append(a)
    else:
        link[a].append(b)
        link[b].append(a)
        link_rev[a].append(b)
        link_rev[b].append(a)


def spfa_min():
    global w
    que = deque()
    que.append(1)
    dis = [0x7fffffff] * (n+1)
    dis[1] = w[1]
    in_que = [0] * (n + 1)
    in_que[1] = 1

    # 进行V次迭代，第V次检查是否是无解情况
    iter_times = 0
    while iter_times < n:
        update_flag = False

        # 利用上一轮迭代距离变小的点进行松弛操作
        node_num = len(que)
        for _ in range(node_num):
            a = que.popleft()
            in_que[a] = 0

            for b in link[a]:
                new_dis = min(dis[a], w[b])
                if new_dis < dis[b]:
                    dis[b] = new_dis
                    update_flag = True

                    if in_que[b] == 0:
                        in_que[b] = 1
                        que.append(b)

        iter_times += 1

        if iter_times == n:
            if update_flag:
                return None

        if not update_flag:
            break

    return [[node, dis[node]] for node in range(1, n + 1)]

def spfa_max():
    global w
    que = deque()
    que.append(n)
    dis = [-0x7fffffff] * (n+1)
    dis[n] = w[n]
    in_que = [0] * (n + 1)
    in_que[n] = 1

    # 进行V次迭代，第V次检查是否是无解情况
    iter_times = 0
    while iter_times < n:
        update_flag = False

        # 利用上一轮迭代距离变小的点进行松弛操作
        node_num = len(que)
        for _ in range(node_num):
            a = que.popleft()
            in_que[a] = 0

            for b in link_rev[a]:
                new_dis = max(dis[a], w[b])
                if new_dis > dis[b]:
                    dis[b] = new_dis
                    update_flag = True

                    if in_que[b] == 0:
                        in_que[b] = 1
                        que.append(b)

        iter_times += 1

        if iter_times == n:
            if update_flag:
                return None

        if not update_flag:
            break

    return [[node, dis[node]] for node in range(1, n + 1)]


min_dist = spfa_min()
max_dist = spfa_max()
# print(min_dist)
# print(max_dist)
ans = 0
for k in range(n):
    ans = max(ans, max_dist[k][1] - min_dist[k][1])
print(ans)