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

using namespace std;

const int MaxN = 55;
const int MaxT = 105;
const int EdgeT[] = {-1, 1};
const int oo = 1000;

vector<int> G[MaxN];
int N, SX, ST, DX, DT, FatherX[MaxN][MaxT], FatherE[MaxN][MaxT],  MaxFlow;
int Cap[MaxN][MaxT][MaxN][2], Flow[MaxN][MaxT][MaxN][2];
queue<int> QX, QT;
int ReqFlow, MinT;

void InitBFS(int StartX, int StartT) {
    memset(FatherX, -1, sizeof(FatherX));
    memset(FatherE, -1, sizeof(FatherE));

    QX.push(StartX), QT.push(StartT);
    FatherX[StartX][StartT] = StartX, FatherE[StartX][StartT] = 0;
}

bool BFS(int StartX, int StartT, int EndX, int EndT) {
    for (InitBFS(StartX, StartT); !QX.empty(); QX.pop(), QT.pop()) {
        int X = QX.front(), T = QT.front();

        for (vector<int>::iterator Y = G[X].begin(); Y != G[X].end(); ++Y) {
            for (int E = 0; E <= 1; ++E) {
                int YT = T+EdgeT[E];
                if (YT >= 0 && YT <= MinT && FatherX[*Y][YT] == -1 && Cap[X][T][*Y][E] > Flow[X][T][*Y][E]) {
                    QX.push(*Y), QT.push(YT);
                    FatherX[*Y][YT] = X, FatherE[*Y][YT] = E;
                }
            }
        }
    }
    return FatherX[EndX][EndT] != -1;
}

void EdmondsKarp() {
    for (int CFlow; BFS(SX, ST, DX, DT); MaxFlow += CFlow) {
        CFlow = oo;
        int X, T, FX, FT, E;
        for (X = DX, T = DT; X != SX || T != ST; X = FX, T = FT) {
            FX = FatherX[X][T], FT = T-EdgeT[FatherE[X][T]], E = FatherE[X][T];
            CFlow = min(CFlow, Cap[FX][FT][X][E]-Flow[FX][FT][X][E]);
        }
        for (X = DX, T = DT; X != SX || T != ST; X = FX, T = FT) {
            FX = FatherX[X][T], FT = T-EdgeT[FatherE[X][T]], E = FatherE[X][T];
            Flow[FX][FT][X][E] += CFlow, Flow[X][T][FX][E^1] -= CFlow;
        }
    }
}

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

void Read() {
    assert(freopen("algola.in", "r", stdin));
    SX = 0, ST = 0, DX = 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[SX].push_back(X), G[X].push_back(SX);
        Cap[SX][ST][X][1] = C;
        ReqFlow += C;
        G[X].push_back(X);
    }
    for (; M; --M) {
        int X, Y, C; assert(scanf("%d %d %d", &X, &Y, &C) == 3);
        G[X].push_back(Y), G[Y].push_back(X);
        for (int T = 0; T <= 2*N; ++T)
            Cap[X][T][Y][1] = Cap[Y][T][X][1] = C;
    }
    for (int X = 1; X <= N; ++X)
        for (int T = 0; T <= 2*N; ++T)
            Cap[X][T][X][1] = oo;
}

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

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