#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cassert>

using namespace std;

const int MaxN = 5050;
const int oo = 110;

vector<int> Network[MaxN], G[MaxN];
int N, S, D, Father[MaxN],  MaxFlow;
char Cap[MaxN][MaxN], Flow[MaxN][MaxN];
queue<int> Q;
int ReqFlow, MinT;

void InitBFS(int Start) {
    for (int X = 0; X < MaxN; ++X)
        Father[X] = -1;
    Q.push(Start), Father[Start] = Start;
}

bool BFS(int Start, int End) {
    for (InitBFS(Start); !Q.empty(); Q.pop()) {
        int X = Q.front();
        for (vector<int>::iterator Y = G[X].begin(); Y != G[X].end(); ++Y)
            if (Father[*Y] == -1 && Cap[X][*Y] > Flow[X][*Y])
                Q.push(*Y), Father[*Y] = X;
    }
    return Father[End] != -1;
}

void EdmondsKarp() {
    for (int CFlow; BFS(S, D); MaxFlow += CFlow) {
        CFlow = oo;
        for (int X = D; X != S; X = Father[X])
            CFlow = min(CFlow, Cap[Father[X]][X]-Flow[Father[X]][X]);
        for (int X = D; X != S; X = Father[X])
            Flow[Father[X]][X] += CFlow, Flow[X][Father[X]] -= CFlow;
    }
}

void BuildGraph() {
    for (int X = 1; X <= N; ++X) {
        for (vector<int>::iterator Y = Network[X].begin(); Y != Network[X].end(); ++Y) {
            int NX = X+(MinT-1)*N, NY = *Y+MinT*N;
            G[NX].push_back(NY), G[NY].push_back(NX);
            Cap[NX][NY] = Cap[X][*Y];
        }
        int NX = X+(MinT-1)*N, NY = X+MinT*N;
        G[NX].push_back(NY), G[NY].push_back(NX);
        Cap[NX][NY] = oo;
    }
    D = 1+MinT*N;
}

void Solve() {
    for (MinT = 1; MaxFlow < ReqFlow; ++MinT) {
        BuildGraph();
        EdmondsKarp();
    }
    --MinT;
}

void Read() {
    assert(freopen("algola.in", "r", stdin));
    S = 0, D = 1;
    int M; assert(scanf("%d %d", &N, &M) == 2);
    for (int X = 1; X <= N; ++X) {
        int C; assert(scanf("%d", &C) == 1);
        G[S].push_back(X), G[X].push_back(S);
        Cap[S][X] = C;
        ReqFlow += C;
    }
    for (; M; --M) {
        int X, Y, C; assert(scanf("%d %d %d", &X, &Y, &C) == 3);
        Network[X].push_back(Y), Network[Y].push_back(X);
        Cap[X][Y] = Cap[Y][X] = C;
    }
}

void Print() {
    assert(freopen("algola.out", "w", stdout));
    printf("%d\n", MinT);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}