# include <cstdio>
# include <cstring>
# include <queue>
# include <vector>
using namespace std;

const char *FIN = "algola.in", *FOU = "algola.out";
const int MAX_N = 55, MAX_H = 5601, MAX = 100;

vector <int> G[MAX_H];
int N, M, mf, suma, D, A[MAX_N], C[MAX_H][MAX_H], F[MAX_H][MAX_H], T[MAX_H];

inline void getmin (int &a, int b) {
    a = a < b ? a : b;
}

inline int bfs (void) {
    memset (T, -1, sizeof (T)), T[1] = 0;
    queue <int> Q;
    for (Q.push (1); ! Q.empty (); Q.pop ()) {
        int X = Q.front ();
        for (vector <int> :: iterator i = G[X].begin (); i != G[X].end (); ++i)
            if (T[*i] == -1 && F[X][*i] < C[X][*i])
                Q.push (*i), T[*i] = X;
    }
    return T[D] != -1;
}

inline void baga (int tip, int x, int y, int z) {
    G[x].push_back (y), G[y].push_back (x);
    if (tip == 0) C[x][y] = z;
    else C[y][x] = z;
}

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d %d", &N, &M);
    for (int i = 1; i <= N; ++i)
        scanf ("%d", A + i);
    for (int i = 2; i <= N; ++i)
        suma += A[i];
    for (int i = 1; i <= N; ++i)
        baga (0, 1, i + 1, A[i]);
    for (int i = 1, x, y, z; i <= M; ++i) {
        scanf ("%d %d %d", &x, &y, &z);
        for (int j = 1; j <= MAX; ++j) {
            baga (0, x + (j - 1) * N + 1, y + j * N + 1, z);
            baga (1, x + j * N + 1, y + (j - 1) * N + 1, z);
        }
    }
    for (int i = 1; i <= MAX; ++i)
        for (int j = 2; j <= N; ++j)
            baga (0, j + (i - 1) * N + 1, j + i * N + 1, MAX_H);

    for (int i = 1; i <= MAX; ++i) {
        D = 2 + i * N;
        for (; bfs ();) {
            for (vector <int> :: iterator i = G[D].begin (); i != G[D].end (); ++i)
                if (F[*i][D] < C[*i][D]) {
                    int fmin = C[*i][D] - F[*i][D];
                    for (int j = *i; T[j]; j = T[j])
                        getmin (fmin, C[T[j]][j] - F[T[j]][j]);
                    F[*i][D] += fmin, F[D][*i] -= fmin;
                    for (int j = *i; T[j]; j = T[j])
                        F[T[j]][j] += fmin, F[j][T[j]] -= fmin;
                    mf += fmin;
                }
        }
        if (mf == suma) {
            fprintf (fopen (FOU, "w"), "%d", i);
            return 0;
        }
    }
}