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

int n, m, a[1005] = { 0 }, hx[1005] = { 0 }, road[1005][1005] = { 0 }, tree[1005][1005] = { 0 }, s[1005] = { 0 };
long long ans = 9e1, sum;

void dfs(int x)
{
    if (hx[x])return;
    if (x == n)
    {
        ans = min(ans, sum);
        return;
    }
    hx[x] = 1;
    sum += a[x];
    for (int i = 1; i <= s[x]; i++)
    {
        sum += road[x][tree[x][i]];
        dfs(tree[x][i]);
        sum -= road[x][tree[x][i]];
    }
    sum -= a[x];
    hx[x] = 0;
    return;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sum = a[1] * (-1);
    while (m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        road[x][y] = z;
        road[y][x] = z;
        s[x]++;
        s[y]++;
        tree[x][s[x]] = y;
        tree[y][s[y]] = x;
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}