#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

ifstream fin ("algola.in"); ofstream fout ("algola.out");

typedef vector< int > graf;

const int nmax = 60;
const int tmax = 100;
const int mmax = 300;
const int inf = (1 << 29);

int S, D, suma, nrm;
int cati[nmax + 1];

struct muchie{
    int x, flux, cap, op;

    muchie() {}
    muchie (int _x, int _cap, int _op) {
        flux = 0, x = _x, cap = _cap, op = _op;
    }
} v[4 * (mmax + nmax) * (tmax + 1)];

graf g[nmax * tmax + 1];
int q[nmax * tmax + 1];
int tata[nmax * tmax + 1], intra[nmax * tmax + 1];

inline int indice (int x, int y) {
    return (x - 1) * (tmax + 1) + y;
}

inline void trage_muchie (int x, int y, int cap) {
    ++ nrm; v[ nrm ] = muchie(y, cap, nrm + 1); g[ x ].push_back( nrm );
    ++ nrm; v[ nrm ] = muchie(x, 0, nrm - 1);   g[ y ].push_back( nrm );
}

void citire() {
    int n, m;
    fin >> n >> m;

    suma = 0;
    for (int i = 1; i <= n; ++ i) {
        fin >> cati[ i ];
        suma += cati[ i ];
    }

    S = indice(n, tmax) + 1;
    for (int i = 1; i <= n; ++ i) {
        int x = indice(i, 0);

        trage_muchie(S, x, cati[ i ]);

        for (int j = 0; j < tmax; ++ j) {
            trage_muchie(indice(i, j), indice(i, j + 1), inf);
        }
    }

    for (int i = 1; i <= m; ++ i) {
        int x, y, cap;
        fin >> x >> y >> cap;
        for (int j = 0; j < tmax; ++ j) {
            trage_muchie(indice(x, j), indice(y, j + 1), cap);
            trage_muchie(indice(y, j), indice(x, j + 1), cap);
        }
    }
}

bool bfs (int t) {
    memset(tata, -1, sizeof(tata));
    tata[ S ] = 0;

    int first, last;
    last = -1;
    first = 0;
    q[ ++ last ] = S;

    while (first <= last) {
        int x = q[ first ++ ];

        if (x % (tmax + 1) > t) continue;

        for (auto i : g[ x ]) {
            if (tata[ v[ i ].x ] == -1 && v[ i ].flux < v[ i ].cap) {
                tata[ v[ i ].x ] = x;
                intra[ v[ i ].x ] = i;
                q[ ++ last ] = v[ i ].x;
            }
        }
    }

    return (tata[ D ] != -1);
}


bool check(int t) {
    for (int i = 1; i <= nrm; ++ i) {
        v[ i ].flux = 0;
    }

    int sol = 0;
    D = indice(1, t);

    while (bfs( t )) {
        for (auto i : g[ D ]) {
            int capat = v[ i ].x;
            muchie aux = v[ v[ i ].op ];

            if (tata[ capat ] != -1 && aux.flux < aux.cap) {
                int fluxmin = aux.cap - aux.flux;
                for (int x = capat; x != S; x = tata[ x ]) {
                    fluxmin = min(fluxmin, v[ intra[ x ] ].cap - v[ intra[ x ] ].flux);
                }

                sol += fluxmin;
                v[ v[ i ].op ].flux += fluxmin;
                v[ i ].flux -= fluxmin;

                for (int x = capat; x != S; x = tata[ x ]) {
                    v[ intra[ x ] ].flux += fluxmin;
                    v[ v[ intra[ x ] ].op ].flux -= fluxmin;
                }
            }
        }
    }

    return (sol == suma);
}

int main() {
    citire();

    int ans = 0;
    for (int step = (1 << 6); step > 0; step >>= 1) {
        if (ans + step <= tmax && !check(ans + step)) {
            ans += step;
        }
    }

    if (cati[ 1 ] == suma) fout << "0\n";
    else fout << ans + 1 << "\n";

    fin.close();
    fout.close();
    return 0;
}