#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <bitset>
using namespace std;
#define NMAX1   110
#define NMAX2   5100
#define maxT    100
#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[100100], GX[100100];

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] = now;
				T[whonext] = min (abs (GG[next].c), T[now]);
				Q[dr ++] = whonext;
				if (whonext == DEST)	return true;
			}
		}
	}
	return false;
}

void make_cap (int a, int b, int c) {
    int i;
    for (i = 0; i < (int) G[a].size(); ++ i)
        if (GG[G[a][i]].b == b) {
            GG[G[a][i]].c += c;
            return;
        }
}

int flux () {
    int FluxTotal = 0, nod;

    while (drum () ) {
	    for (nod = DEST; nod != SOURCE; nod = P[nod]) {
            make_cap(P[nod], nod, - T[DEST]);
            make_cap(nod, P[nod], T[DEST]);
		}
		FluxTotal += T[DEST];
    }
	return FluxTotal;
}

void copy () {
    int i;
    for (i = 1; i <= Nr; ++ i)
        GG[i] = GX[i];
}

void cautbin() {
    int p, u, m, ret;
    p = 1; u = maxT; m = (1 + maxT) / 2;

    while (p < u) {
        maxL = 2 + (m + 1) * N;
        copy();
        ret = flux();
        if (ret == sum)
            u = m - 1;
        else
            p = m + 1;
        m = (p + u) / 2;
    }

    for (maxL = 3 * (m + 1) * N; flux () != sum; ++ m);
    printf("%d\n", m);
}

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);
}

int main(){
    int i, nod1, nod2, j;

    freopen("algola.in", "r", stdin);
    freopen("algola.out", "w", stdout);

    scanf("%d %d", &N, &M);

    for (i = 1; i <= N; ++ i) {
        scanf("%d", &A[i]);
        sum += (i > 1) ? A[i] : 0;
    }

    for (i = 1; i <= M; ++i)
        scanf("%d %d %d", &B[i].a, &B[i].b, &B[i].c);

    SOURCE = 1; DEST = 2;
    for (i = 0; i < maxT; ++ i) {
        nod1 = 3 + N + i * N;
        make_link(nod1, DEST, oo2);
        make_link(DEST, nod1, oo2);
    }

    for (i = 2; i <= N; ++ i) {
        nod1 = 2 + i;
        make_link(SOURCE, nod1, A[i]);
        make_link(nod1, SOURCE, A[i]);
        for (j = 0; j < maxT; ++ j) {
            nod1 = 2 + i;
            nod2 = 2 + N + j * N + i;
            make_link(nod1, nod2, A[i]);
            make_link(nod2, nod1, A[i]);
            if (j + 1 < maxT) {
                nod1 = 2 + (j + 1) * N + i;
                make_link(nod1, nod2, oo2);
                make_link(nod2, nod1, oo2);
            }
        }
    }

    for (i = 1; i <= M; ++ i)
        for (j = 0; j < maxT - 1; ++ j) {
            nod1 = 2 + N + j * N + B[i].a;
            nod2 = 2 + N + (j + 1) * N + B[i].b;
            make_link(nod1, nod2, B[i].c);
            make_link(nod2, nod1, B[i].c);
            
            nod1 = 2 + N + j * N + B[i].b;
            nod2 = 2 + N + (j + 1) * N + B[i].a;
            make_link(nod1, nod2, B[i].c);
            make_link(nod2, nod1, B[i].c);
        }

    cautbin();
}