#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int MAXN = 51;
const int MAXM = 301;
const int MAXT = 101;
const int MAX = MAXN * (MAXT + 1);
#define conv(a, b) ( (b) * MAXN + a )

int n, m, i, j, x, y, k, SOL, FLOW, sum;
struct sedge { int x, y, k; } edge[MAXM];
int deg[MAXN];
int *con[MAXN];
char c[MAXN][MAXN];
char C[MAX][MAX];
int q[MAX], up[MAX], min[MAX], l, r;

void inline insert(int next, int cur2)
{
    min[next] = min[cur2] <= C[cur2][next] ? min[cur2] : C[cur2][next];
    up[next] = cur2;
    q[++r] = next;
}

int flow()
{
    int cur, curt, next, cur2, curflow, b = 0, *p;
    memset(q, 0, sizeof(q));
    memset(min, 0, sizeof(min));
    
    for (q[l = r = 0] = 0, min[0] = sum; l <= r && !b; l++)
    {
        cur = q[l] % MAXN; curt = q[l] / MAXN;
        cur2 = conv(cur, curt);
        for (p = con[cur]; *p != -1 && !b; p++)
        {
            next = conv(*p, curt + 1);
            if (curt <= SOL && min[next] == 0 && C[cur2][next])
            {
                insert(next, cur2);
                if (*p == 1)
                {
                    b = curt + 1;
                    break;
                }
            }
            next = conv(*p, curt - 1);
            if (curt > 0 && min[next] == 0 && C[cur2][next])
            {
                insert(next, cur2);
                if (*p == 1)
                    b = curt - 1;
            }
        }
        next = conv(cur, curt + 1);
        if (curt <= SOL && min[next] == 0 && C[cur2][next])
            insert(next, cur2);
    }
    
    if (!b) return 0;       
    curflow = min[ conv(1, b) ];
    FLOW += curflow;
    for (i = 1, j = b; i; )
    {
        k = conv(i, j);
        C[ up[k] ][k] -= curflow;
        C[k][ up[k] ] += curflow;
        
        i = up[k] % MAXN;
        j = up[k] / MAXN;
    }
    return 1;
}

int main()
{
    freopen("algola.in", "rt", stdin);
    freopen("algola.out", "wt", stdout);
    scanf("%d %d", &n, &m);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &c[0][i]);
        sum += c[0][i];
        if (c[0][i])
        {
            deg[0]++; deg[i]++;
            c[i][0] = c[0][i];
        }
    }
    for (i = 0; i < m; i++)
    {
        scanf("%d %d %d", &x, &y, &k);
        c[x][y] = (c[y][x] += k);
        deg[x]++; deg[y]++;
        edge[i].x = x; edge[i].y = y; edge[i].k = k;
    }
    for (i = 0; i <= n; deg[i] = -1, i++)
        con[i] = (int *) calloc(deg[i] + 1, sizeof(int));
    for (i = 1; i <= n; i++)
        if (c[0][i])
             con[0][++deg[0]] = i,
             con[i][++deg[i]] = 0;
    for (i = 0; i < m; i++)
    {
        x = edge[i].x; y = edge[i].y; k = edge[i].k;
        con[x][++deg[x]] = y;
        con[y][++deg[y]] = x;
    }
    for (i = 0; i <= n; i++)
        con[i][deg[i] + 1] = -1;

    // construire graf
    for (i = 1; i <= n; i++)
        for (j = 0; j < MAXT; j++)
        {
            C[conv(i, j)][conv(i, j + 1)] = sum;
            for (k = 0; k <= deg[i]; k ++)
                C[conv(i, j)][conv(con[i][k], j + 1)] = c[i][ con[i][k] ];
        }
    for (k = 0; k <= deg[0]; k ++)
        C[0][conv(con[0][k], 1)] = c[0][ con[0][k] ];

    //flux
    for (SOL = 1; FLOW < sum; SOL++)
        while ( flow() );
    
    printf("%d\n", SOL - 1);
    return 0;
}