#include <stdio.h>

#define MAX_N 51
#define MAX_T 101
#define code(n, t) ((n) * MAX_T + (t))
#define NIL -1
#define START -2
#define INF 1000000666
#define FIN "algola.in"
#define FOUT "algola.out"
#define min(a, b) ((a) < (b) ? (a) : (b))
#define enqueue if (R[crt][next] > 0 && up[next] == NIL) \
                { \
                    up[Q[++qr] = next] = crt; \
                    flow[next] = min(flow[crt], R[crt][next]); \
                    if (next / MAX_T == 1) return next; \
                } \


int N, M, A[MAX_N], G[MAX_N][MAX_N], deg[MAX_N], C[MAX_N][MAX_N], Res;
char R[MAX_N * MAX_T][MAX_N * MAX_T];

int Q[MAX_N * MAX_T], up[MAX_N * MAX_T], flow[MAX_N * MAX_T];

int augument(int time_limit)
{
    int i, n, t, ql, qr, crt, next;

    for (i = 0; i <= (N + 1) * MAX_T; i++)
        up[i] = NIL, flow[i] = INF;
        
    for (up[Q[ql = qr = 0] = 0] = START; ql <= qr; ql++)
    {
        crt = Q[ql], n = crt / MAX_T, t = crt % MAX_T;

        if (t + 1 <= time_limit)
        {
            next = code(n, t + 1);
            enqueue;
        }
        if (t > 0)
        {
           next = code(n, t - 1);
           enqueue;
        }

        for (i = 0; i < deg[n]; i++)
        {
            if (t + 1 <= time_limit)
            {
                next = code(G[n][i], t + 1);
                enqueue;
            }
            if (t > 0)
            {
                next = code(G[n][i], t - 1);
                enqueue;
            }
        }
    }
    return NIL;
}

int main(void)
{
    int i, j, k, c, n, sum = 0;
    
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d %d", &N, &M);
    for (i = 1; i <= N; i++)
        scanf("%d", A + i), sum += A[i];
    for (; M > 0; M--)
    {
        scanf("%d %d %d", &i, &j, &c);
        G[i][deg[i]++] = j;
        G[j][deg[j]++] = i;
        C[i][j] = C[j][i] = c;
    }

    for (i = 1; i <= N; i++)
        for (j = 0; j + 1 < MAX_T; j++)
        {
            n = code(i, j);
            R[n][code(i, j + 1)] = sum;
            for (k = 0; k < deg[i]; k++)
                R[n][code(G[i][k], j + 1)] = C[i][G[i][k]];
        }
    for (i = 1; i <= N; i++)
    {
        R[0][code(i, 1)] = A[i];
        G[0][deg[0]++] = i;
    }

    for (Res = 1; ; Res++)
    {
        for (; (j = augument(Res)) != -1; sum -= flow[j])
            for (i = j; i > 0; i = up[i])
                R[up[i]][i] -= flow[j],
                R[i][up[i]] += flow[j];
        if (!sum) break;
    }

    printf("%d\n", Res - 1);

    return 0;
}