#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int INF = 2147483647;
int n, m;
int p[MAXN + 5]; // 价格
// i 原点 ~ i+n 买完之后的 ~ i+n+n 卖完之后的
vector<pair<int, int>> e[MAXN * 3 + 5];
// spfa
int dis[MAXN * 3 + 5];  // 最短路
bool vis[MAXN * 3 + 5]; // 在不在队列里
queue<int> q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
        e[i].push_back({i + n, p[i]});
        e[i + n].push_back({i + n + n, -p[i]});
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v, op;
        cin >> u >> v >> op;
        e[u].push_back({v, 0});
        e[u + n].push_back({v + n, 0});
        e[u + n + n].push_back({v + n + n, 0});
        if (op == 2)
        {
            e[v].push_back({u, 0});
            e[v + n].push_back({u + n, 0});
            e[v + n + n].push_back({u + n + n, 0});
        }
    }
    // SPFA
    for (int i = 1; i <= 3 * n; i++)
    {
        dis[i] = INF;
        vis[i] = false;
    }
    dis[1] = 0;
    vis[1] = true;
    q.push(1);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                if (!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    cout << -dis[n + n + n];
    return 0;
}