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

#define MAXN 51
#define MAXT 102
#define MAXR MAXN*MAXT + 100
#define fun(a, b) ( (b) * 51 + a )
#define min(a, b) ( (a) > (b) ? (b) : (a) )

int N, M, A[MAXN], nr[MAXN], sum, max_flow, l, r, sink;
int vec[MAXN][MAXN], cap[MAXN][MAXN], sol;
char C[MAXR][MAXR], F[MAXR];
int Q[MAXR], U[MAXR];

void drop(char *mess)
{
    printf("%s\n", mess);
    exit(1);
}

void read_data()
{
    int i, a, b, c;
    
    FILE *f = fopen("algola.in", "rt");
    
    fscanf(f, "%d %d", &N, &M);
    if (N > 50 || M > 300)
        drop("err1");
        
    sink = 1;
    
    for (i = 1; i <= N; i ++)
        fscanf(f, "%d", A + i),
        sum += A[i];
        
    if (sum > 50)
       drop("err2");

    for (i = 1; i <= N; i ++)
    if (A[i])
    {
        vec[0][nr[0] ++] = i;
        vec[i][nr[i] ++] = 0;
        cap[0][i] = cap[i][0] = c;
    }
    
    for (i = 0; i < M; i ++)
    {
        if (fscanf(f, "%d %d %d", &a, &b, &c) != 3)
           drop("err0");
        vec[a][nr[a] ++] = b,
        vec[b][nr[b] ++] = a;
        if (a == b || a < 1 || a > N || b < 1 || b > N)
           drop("err3");
           
        if (cap[a][b])
           drop("err4");
           
        cap[b][a] = cap[a][b] = c;
    }
    fclose(f);
}

int BFS()
{
    int i, j, k, crt, tc, f_nxt, f_crt, gas = 0;
    
    /* sterge */
    memset(F, 0, sizeof(F));
        
    /* init */
    Q[l = r = 0] = 0;
    F[0] = sum;
    
    for (; l <= r && !gas; l ++)
    {
        crt = Q[l] % 51, tc = Q[l] / 51;
        f_crt = fun(crt, tc);
        
        for (i = 0; i < nr[crt] && !gas; i ++)
        {
            f_nxt = fun(vec[crt][i], tc + 1);
            if (tc <= sol && F[f_nxt] == 0 && C[f_crt][f_nxt])
            {
                F[f_nxt] = min(F[f_crt], C[f_crt][f_nxt]);
                U[f_nxt] = f_crt;
                Q[ ++ r] = f_nxt;
                
                if (vec[crt][i] == sink)
                {
                   gas = tc + 1;
                   break;
                }
            }
            f_nxt = fun(vec[crt][i], tc - 1);
            if (tc > 0 && F[f_nxt] == 0 && C[f_crt][f_nxt])
            {
                F[f_nxt] = min(F[f_crt], C[f_crt][f_nxt]);
                U[f_nxt] = f_crt;
                Q[ ++ r] = f_nxt;
                if (vec[crt][i] == sink)
                {
                   gas = tc - 1;
                   break;
                }
            }
        }
            f_nxt = fun(crt, tc + 1);
            if (tc <= sol && F[f_nxt] == 0 && C[f_crt][f_nxt])
            {
                F[f_nxt] = min(F[f_crt], C[f_crt][f_nxt]);
                U[f_nxt] = f_crt;
                Q[ ++ r] = f_nxt;
            }
    }
    
    if (gas == 0)
       return 0;
       
    int hey = F[fun(sink, gas)];
    max_flow += hey;
    for (i = sink, j = gas; i;)
    {
        k = fun(i, j);
        C[U[k]][k] -= hey;
        C[k][U[k]] += hey;
        
        i = U[k] % 51;
        j = U[k] / 51;
    }
    return 1;
}

void solve()
{
    int i, j, k;
    
    /* construim graful */
    for (i = 1; i <= N; i ++)
    for (j = 0; j < MAXT; j ++)
    {
        C[fun(i, j)][fun(i, j + 1)] = sum;
        for (k = 0; k < nr[i]; k ++)
            C[fun(i, j)][fun(vec[i][k], j + 1)] = cap[i][ vec[i][k] ];
    }
    for (k = 0; k < nr[0]; k ++)
        C[fun(0, 0)][fun(vec[0][k], 1)] = A[vec[0][k]];

    /* flux incremental: reducem factorul log(maxv) */
    for (sol = 1; max_flow < sum; sol ++)
        while (BFS())
         ;
}

void write_data()
{
    FILE *f = fopen("algola.out", "wt");
    fprintf(f, "%d\n", sol - 1);
    fclose(f);
}

int main()
{
    read_data();
    solve();
    write_data();
    return 0;
}