#include <bits/stdc++.h>
#define maxN 52
#define maxM 302
#define maxT 102
#define maxG 5002
#define inf 1000000000
using namespace std;

FILE *fin = freopen("algola.in", "r", stdin);
FILE *fout = freopen("algola.out", "w", stdout);

/* ================= */
int n, m, N, S, D, sum;
/* ================= */
vector < int > V[maxN];
struct Node
{
    int x, t;
};
queue < Node > Bf;
bool vis[maxG];

int idx[maxN][maxT], R[maxG][maxG], r[maxG][maxG], deUnde[maxG], c[maxN][maxN];
queue < int > Q;

/* ================= */
int ans;
/* ================= */

void BFS(int S, int D)
{
    memset(deUnde, 0, sizeof(deUnde));
    Q.push(S);
    deUnde[S] = S;
    deUnde[D] = D;
    while (!Q.empty())
    {
        int x = Q.front();

        Q.pop();
        for (int i = 1; i <= N; ++ i)
            if (r[x][i] > 0 && deUnde[i] == 0)
            {
                deUnde[i] = x;
                Q.push(i);
            }
    }
}


int maxFlow()
{
    int ans = 0;
    memcpy(R, r, sizeof(r));
    bool continua = true;
    while (continua)
    {
        BFS(S, D);
        continua = false;
        for(int u = 1; u <= N; u++)
            if (r[u][D] > 0 && deUnde[u] != 0 && u != D)
            {
                continua = true;
                deUnde[D] = u;
                int nod = D;
                int cap = inf;
                while (nod != S)
                {
                    cap = min(cap, r[deUnde[nod]][nod]);
                    nod = deUnde[nod];
                }
                nod = D;
                ans += cap;
                while (nod != S)
                {
                    r[deUnde[nod]][nod] -= cap;
                    r[nod][deUnde[nod]] += cap;
                    nod = deUnde[nod];
                }
            }
    }
    memcpy(r, R, sizeof(R));
    return ans;
}

void precomp()
{
    for (int i = 0; i <= n; ++ i)
        for (int t = 0; t < maxT; ++ t)
            idx[i][t] = t * (n + 1) + i + 1;
}

void CompGraph()
{
    for (int i = 0; i <= n; ++ i)
        Bf.push({i, 0});
    while (!Bf.empty())
    {
        Node nod = Bf.front();
        int crtNod = idx[nod.x][nod.t];
        Bf.pop();
        if (nod.t < maxT - 1)
        {
            int nxtNod = idx[nod.x][nod.t + 1];
            r[crtNod][nxtNod] = inf;

            if (!vis[nxtNod])
            {
                vis[nxtNod] = 1;
                Bf.push({nod.x, nod.t + 1});
            }
        }
        for (int son : V[nod.x])
        {
            r[crtNod][idx[son][nod.t + 1]] = c[nod.x][son];
            if (!vis[idx[son][nod.t + 1]])
                Bf.push({son, nod.t + 1});
            vis[idx[son][nod.t + 1]] = 1;
        }
    }
}

int bs()
{
    int i = maxT - 1, p = 1 << 6;
    while (p)
    {
        N = D = idx[1][i - p];
        if (i > p && maxFlow() >= sum)
            i -= p;
        p >>= 1;
    }
    return i;
}

int main()
{
    scanf("%d %d", &n, &m);

    precomp();
    S = 1;

    for (int i = 1; i <= n; ++ i)
    {
        int cap;
        scanf("%d", &cap);
        sum += cap;
        r[1][idx[i][0]] = cap;
    }
    for (int i = 1; i <= m; ++ i)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        scanf("%d", &c[x][y]);
        c[y][x] = c[x][y];
        V[x].push_back(y);
        V[y].push_back(x);
    }
    CompGraph();

    ans = bs();
    printf("%d\n", ans);
    return 0;
}