#include <cstdio>
#include <cstdlib>
#include <vector>
#define maxn 54
#define maxp 6010
#define inf 0x3f3f3f3f
using namespace std;
int n, m, i, j, src, dst, suma, a, b, cc;
int v[maxn];
vector <int> g[maxn], tt[maxn];
vector <int> x[maxp];
char c[maxp][maxp];
int flux[maxp], up[maxp];
int sol, ok;
void build_graph() {
int t, fiu;
src = 0; dst = 1;
for (t = 100; t > 0; t--) {
for (i = 1; i <= n; i++) {
x[t * n + i].push_back((t - 1) * n + i);
x[(t - 1) * n + i].push_back(t * n + i);
for (j = 0; j < g[i].size(); j++) {
fiu = g[i][j];
x[t * n + i].push_back((t - 1) * n + fiu);
x[(t - 1) * n + fiu].push_back(t * n + i);
}
}
}
for (i = 1; i <= 1; i++) {
x[i].push_back(dst);
x[dst].push_back(i);
}
//TODO: cand fac fluxul sa nu uit sa numar separat pentru fiecare nod de la t = 0, nu pot merge in destinatie pentru ca e 6000 :)
}
inline int min(int a, int b) {
if (a < b)
return a;
return b;
}
inline void build(int t) {
int i, j, k, fiu;
x[src].clear();
for (i = 1; i <= n; i++) {
// x[i].push_back(dst);
// x[dst].push_back(i);
c[i][dst] = inf;
x[src].push_back(t * n + i);
x[t * n + i].push_back(src);
c[src][t * n + i] = v[i];
}
for (k = t; k > 0; k--) {
for (i = 1; i <= n; i++) {
c[k * n + i][(k - 1) * n + i] = inf;
for (j = 0; j < g[i].size(); j++) {
fiu = g[i][j];
c[k * n + i][(k - 1) * n + fiu] = tt[i][j];
}
}
}
}
inline void init() {
memset(up, -1, sizeof(up));
memset(flux, 0, sizeof(flux));
flux[src] = inf;
}
inline int bf() {
int p, u;
int nod, fiu;
int q[maxp];
p = u = 1;
q[u] = src;
while (p <= u) {
nod = q[p];
for (i = 0; i < x[nod].size(); i++) {
fiu = x[nod][i];
if (flux[fiu] == 0 && c[nod][fiu] > 0) {
flux[fiu] = min(flux[nod], c[nod][fiu]);
// fprintf(stderr, "%d -> %d\n", nod, fiu);
q[++u] = fiu;
up[fiu] = nod;
if (fiu == dst) {
p = u + 1;
break;
}
}
}
p++;
}
if (flux[dst] == 0) {
ok = 0;
return 0;
}
ok = 1;
for (i = dst; i != src; i = up[i]) {
// fprintf(stderr, "%d ", i);
c[up[i]][i] -= flux[dst];
c[i][up[i]] += flux[dst];
}
// fprintf(stderr, "\n%d\n", flux[dst]);
return flux[dst];
}
inline bool posibil(int t) {
int ff, i;
build(t);
/* for (i = 0; i <= (t + 1) * n; i++) {
printf("%d --> ", i);
for (j = 0; j < x[i].size(); j++)
printf("%d ", x[i][j]);
printf("\n");
}*/
ok = 1; ff = 0;
while (ok) {
init();
ff += bf();
}
for (i = 1; i <= n; i++)
x[t * n + i].pop_back();
if (ff == suma)
return true;
return false;
}
void bsearch(int left, int right) {
int m;
while (left <= right) {
m = (left + right) / 2;
// fprintf(stderr, "%d %d\n", m, posibil(m));
if (posibil(m)) {
sol = min(sol, m);
right = m - 1;
}
else
left = m + 1;
}
}
int main() {
freopen("algola.in", "r", stdin);
freopen("algola.out", "w", stdout);
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++) {
scanf("%d", &v[i]);
suma += v[i];
}
for (i = 1; i <= n; i++) {
scanf("%d%d%d", &a, &b, &cc);
g[a].push_back(b);
tt[a].push_back(cc);
g[b].push_back(a);
tt[b].push_back(cc);
}
build_graph();
sol = inf;
bsearch(1, 100);
printf("%d\n", sol);
return 0;
}