#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
#define itEdge vector <EDGE>::iterator
#define itInt vector <int>::iterator
const int INF = 2e9, NMAX = 2510, source = 0;
int n, ans, cap[NMAX][NMAX], flow[NMAX][NMAX], vis[NMAX], dad[NMAX];
struct EDGE {
int node, lim;
EDGE (int node, int lim) {
this->node = node;
this->lim = lim;
}
};
vector <EDGE> orig[NMAX];
vector <int> graph[NMAX];
bool bfs (int source, int sink) {
itInt it;
queue <int> q;
int node;
memset(vis, 0, sizeof(vis));
memset(dad, 0, sizeof(dad));
q.push(source);
vis[source] = 1;
while(!q.empty()) {
node = q.front();
q.pop();
if(node == sink)
continue;
for(it = graph[node].begin(); it != graph[node].end(); ++ it)
if(!vis[*it] && cap[node][*it] > flow[node][*it]) {
q.push(*it);
dad[*it] = node;
vis[*it] = 1;
}
}
return vis[sink];
}
int maxFlow (int source, int sink) {
itInt it;
int node, minFlow;
while(bfs(source, sink)) {
for(it = graph[sink].begin(); it != graph[sink].end(); ++ it) {
if(!vis[*it])
continue;
dad[sink] = *it;
node = sink;
minFlow = INF;
while(node != source) {
minFlow = min(minFlow, cap[dad[node]][node] - flow[dad[node]][node]);
node = dad[node];
}
node = sink;
while(node != source) {
flow[dad[node]][node] += minFlow;
flow[node][dad[node]] -= minFlow;
node = dad[node];
}
ans += minFlow;
}
}
return ans;
}
int code (int node, int t) {
return node + t * n;
}
void drawEdge (int a, int b, int lim) {
graph[a].push_back(b);
graph[b].push_back(a);
cap[a][b] = lim;
}
int main() {
freopen("algola.in", "r", stdin);
freopen("algola.out", "w", stdout);
itEdge it;
int nPers, sink, m, i, x, node, y, c, t;
scanf("%d%d", &n, &m);
nPers = 0;
for(i = 1; i <= n; ++ i) {
scanf("%d", &c);
drawEdge(source, i, c);
nPers += c;
}
for(i = 1; i <= m; ++ i) {
scanf("%d%d%d", &x, &y, &c);
orig[x].push_back(EDGE(y, c));
orig[y].push_back(EDGE(x, c));
}
t = 0;
while(t <= 50) {
for(i = 1; i <= n; ++ i) {
drawEdge(code(i, t), code(i, t + 1), INF);
for(it = orig[i].begin(); it != orig[i].end(); ++ it)
drawEdge(code(i, t), code(it->node, t + 1), it->lim);
}
sink = code(1, t + 1);
if(maxFlow(source, sink) >= nPers) {
printf("%d\n", t + 1);
return 0;
}
++ t;
}
return 0;
}