#include <bits/stdc++.h>
#define maxN 52
#define maxM 302
#define maxT 100
#define maxG 5102
#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], Adj[maxG];

bool vis[maxG];

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

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

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

        Q.pop();
        for (int i : Adj[x])
            if (r[x][i] > 0 && deUnde[i] == -1)
            {
                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 : Adj[D])
            if (r[u][D] > 0 && deUnde[u] != -1 && 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 addEdge(int x, int y, int cap)
{
    r[x][y] = cap;
    Adj[x].push_back(y);
    Adj[y].push_back(x);
}

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

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 = 0;

    for (int i = 1; i <= n; ++ i)
    {
        int cap;
        scanf("%d", &cap);
        sum += cap;
        r[S][idx[i][0]] = cap;
        Adj[S].push_back(idx[i][0]);
        Adj[idx[i][0]].push_back(S);
        for (int t = 0; t < maxT - 1; ++ t)
            addEdge(idx[i][t], idx[i][t + 1], inf);

    }
    for (int i = 1; i <= m; ++ i)
    {
        int x, y, cap;
        scanf("%d %d %d", &x, &y, &cap);
        if (x > y)
            swap(x, y);
        for (int t = 0; t < maxT - 1; ++ t)
        {
            addEdge(idx[x][t], idx[y][t + 1], cap);
            addEdge(idx[y][t], idx[x][t + 1], cap);
        }
        if (x == 1)
            addEdge(idx[x][maxT - 1], idx[y][maxT], cap);

    }
    //CompGraph();

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