#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<queue>
using namespace std;

int n, m, a[1005] = { 0 }, f[1005], road[1005][1005], tree[1005][1005], s[1005] = { 0 }, hx[1005][1005] = { 0 };
queue<int>que;

int main()
{
    int x, y, z;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)f[i] = 1e9;
    while (m--)
    {
        cin >> x >> y >> z;
        road[x][y] = z + a[x];
        road[y][x] = z + a[y];
        s[x]++;
        s[y]++;
        tree[x][s[x]] = y;
        tree[y][s[y]] = x;
    }
    que.push(1);
    f[1] = 0;
    while (!que.empty())
    {
        x = que.front();
        for (int i = 1; i <= s[x]; i++)
        {
            y = tree[x][i];
            if (hx[x][y])continue;
            que.push(y);
            f[y] = min(f[y], road[x][y] + f[x]);
            hx[y][x] = 1;
            hx[x][y] = 1;
        }
        que.pop();
    }
    cout << f[n]-a[1] << endl;
    return 0;
}