#include <bits/stdc++.h>
#define maxN 62
#define maxM 302
#define maxT 100
#define maxG 6102
#define maxE maxG + maxM * maxT
#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, nrE;
/* ================= */
vector < int > V[maxN], Adj[maxG];
int idx[maxN][maxT];
struct Edge
{
    int nod, cap, r, idxO;
} edge[maxE];

int in[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 (edge[i].r > 0 && deUnde[edge[i].nod] == -1 && edge[i].nod <= N)
            {
                deUnde[edge[i].nod] = x;
                in[edge[i].nod] = i; // r[deUnde[nod]][nod]
                Q.push(edge[i].nod);
            }
    }
}


int maxFlow()
{
    int ans = 0;
    for (int i = 1; i <= nrE; ++ i)
        edge[i].r = edge[i].cap;
    bool continua = true;
    while (continua)
    {
        BFS(S, D);
        continua = false;
        for (int u : Adj[D])
            if (edge[u].nod < D && edge[edge[u].idxO].r > 0 && deUnde[edge[u].nod] != -1 && edge[u].nod != D)
            {
                continua = true;
                //deUnde[D] = edge[u].nod;
                int nod = edge[u].nod;
                int cap = edge[edge[u].idxO].r;
                while (nod != S)
                {
                    cap = min(cap, edge[in[nod]].r);
                    nod = deUnde[nod];
                }
                nod = edge[u].nod;
                ans += cap;
                edge[edge[u].idxO].r -= cap;
                edge[u].r += cap;
                while (nod != S)
                {
                    edge[in[nod]].r -= cap;
                    edge[edge[in[nod]].idxO].r += cap;
                    nod = deUnde[nod];
                }
            }
    }

    return ans;
}

void addEdge(int x, int y, int cap)
{
    edge[++ nrE] = {y, cap, cap, nrE + 1};
    edge[++ nrE] = {x, 0, 0, nrE - 1};
    Adj[x].push_back(nrE - 1);
    Adj[y].push_back(nrE);
}

void precomp()
{
    idx[0][0] = 0;
    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)
    {
        if (i > 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;
        addEdge(S, idx[i][0], cap);

        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[y][maxT - 1], idx[x][maxT], cap);
    }
    //CompGraph();

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