#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <bitset>
#include <assert.h>
using namespace std;
#define NMAX1   310
#define NMAX2   5500
#define maxT    101
#define oo      1000000
#define oo2     10000
int N, M;
vector <int> G[NMAX2];
int SOURCE, DEST, P[NMAX2], T[NMAX2], A[NMAX2], maxL, sum, Q[NMAX2], Nr, C[200100];
 
struct muchie {
    int a, b, c;
} B[NMAX1], GG[200100];
 
inline int min (int a,int b){
    return (a < b) ? a : b;
}
 
bool drum () {
    int st, dr, i, now, next, whonext;
 
    memset (P, 0, sizeof(P));
    memset (T, 0, sizeof(T));
    Q[st = 0] = SOURCE; dr = 1;
    T[SOURCE] = oo; P[SOURCE] = -1;
 
    while (st < dr) {
        now = Q[st ++ ];
        for (i = 0; i < (int) G[now].size (); ++ i) {
            next = G[now][i];
            whonext = GG[next].b;
            if (whonext > maxL) continue;
            if (! P[whonext] && GG[next].c > 0) {
                P[whonext] = next;
                T[whonext] = min (GG[next].c, T[now]);
                Q[dr ++] = whonext;
                if (whonext == DEST)    return true;
            }
        }
    }
    return false;
}
 
int flux () {
    int FluxTotal = 0, nod, mu;
 
    while (drum () ) {
        for (nod = DEST; nod != SOURCE; nod = GG[P[nod]].a) {
            mu = P[nod];
            assert(GG[mu].a <= maxL);
            assert(GG[mu].b <= maxL);
            GG[mu].c -= T[DEST];
            GG[ (mu % 2) ? (mu + 1) : (mu - 1)].c += T[DEST];
    //        printf("%d ", nod);
        }
//        printf("1\n");
  //      printf("%d\n", T[DEST]);
        FluxTotal += T[DEST];
    }
    return FluxTotal;
}
 
void copy () {
    int i;
    for (i = 1; i <= Nr; ++ i)
        GG[i].c = C[i];
}
 
void cautbin() {
    int p, u, m, ret, last = oo;
    p = 0; u = maxT - 1;
                                 
    while (p <= u) {
        m = (p + u) / 2;
        maxL = 2 + m * N;
        copy();
        DEST = 2 + m * N;
        ret = flux();
   //     fprintf(stderr, "%d %d\n", m, ret);
        if (ret == sum) {
            u = m - 1;
            last = m;
        }
        else
            p = m + 1;
    }
    
    //for (maxL = 2 + p * N, copy(), DEST = 2 + p * N; flux () != sum; ++ m);
    printf("%d\n", last);
}
 
void make_link(int a, int b, int c) {
    ++ Nr;
    GG[Nr].a = a;
    GG[Nr].b = b;
    C[Nr] = c;
    G[a].push_back(Nr);
    ++ Nr;
    GG[Nr].a = b;
    GG[Nr].b = a;
    C[Nr] = 0;
    G[b].push_back(Nr);
}
 
int main(){
    int i, nod1, nod2, j;
 
    freopen("algola.in", "r", stdin);
    freopen("algola.out", "w", stdout);
 
    scanf("%u%u", &N, &M);
 
    for (i = 1; i <= N; ++ i) {
        scanf("%u", &A[i]);
        sum += (i > 1) ? A[i] : 0;
    }
 
    for (i = 1; i <= M; ++i)
        scanf("%u%u%u", &B[i].a, &B[i].b, &B[i].c);
 
    SOURCE = 1;
            
    for (i = 1; i <= N; ++ i) {
        nod1 = 1 + i;
        make_link(SOURCE, nod1, A[i]);
        for (j = 0; j + 1 < maxT; ++ j) {
            nod1 = 1 + j * N + i;
            nod2 = 1 + (j + 1) * N + i;
            make_link(nod1, nod2, oo);
        }
    }
             
    for (i = 1; i <= M; ++ i)
        for (j = 0; j + 1 < maxT; ++ j) {
            nod1 = 1 + j * N + B[i].a;
            nod2 = 1 + (j + 1) * N + B[i].b;
            make_link(nod1, nod2, B[i].c);
             
            nod1 = 1 + j * N + B[i].b;
            nod2 = 1 + (j + 1) * N + B[i].a;
            make_link(nod1, nod2, B[i].c);
        }
              
    cautbin();
}