#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;

struct muchie {
    int a, b, c;
} B[NMAX1], GG[200100], GX[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 = GX[i].c;
}

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;
    GX[Nr].a = a;
    GX[Nr].b = b;
    GX[Nr].c = c;
    G[a].push_back(Nr);
    ++ Nr;
    GX[Nr].a = b;
    GX[Nr].b = a;
    GX[Nr].c = 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();
}