#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;

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

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

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

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);

        v[ nrm ] = muchie(x, cati[ i ]); g[ S ].push_back( nrm ); ++ nrm;
        v[ nrm ] = muchie(S, 0);         g[ x ].push_back( nrm ); ++ nrm;

        for (int j = 0; j < tmax; ++ j) {
            v[ nrm ] = muchie(indice(i, j + 1), inf); g[ indice(i, j) ].push_back( nrm ); ++ nrm;
            v[ nrm ] = muchie(indice(i, j), 0);   g[ indice(i, j + 1) ].push_back( nrm ); ++ nrm;
        }
    }

    for (int i = 1; i <= m; ++ i) {
        int x, y, cap;
        fin >> x >> y >> cap;
        for (int j = 0; j < tmax; ++ j) {
            v[ nrm ] = muchie(indice(y, j + 1), cap); g[ indice(x, j) ].push_back( nrm ); ++ nrm;
            v[ nrm ] = muchie(indice(x, j), 0);   g[ indice(y, j + 1) ].push_back( nrm ); ++ nrm;

            v[ nrm ] = muchie(indice(x, j + 1), cap); g[ indice(y, j) ].push_back( nrm ); ++ nrm;
            v[ nrm ] = muchie(indice(y, j), 0);   g[ indice(x, j + 1) ].push_back( nrm ); ++ nrm;
        }
    }
}

bool bfs() {
    memset(tata, -1, sizeof(tata));
    q.push( S );
    tata[ S ] = 0;

    while (!q.empty()) {
        int x = q.front(); q.pop();

        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.push( 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()) {
        for (auto i : g[ D ]) {
            int capat = v[i ^ 1].x;
            muchie aux = v[i ^ 1];

            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[i ^ 1].flux += fluxmin;
                v[ i ].flux -= fluxmin;

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

    return (sol == suma);
}

int main() {
    citire();

    int ans = tmax;
    for (int step = (1 << 6); step > 0; step >>= 1) {
        if (ans - step >= 0 && check(ans - step)) {
            ans -= step;
        }
    }
    fout << ans << "\n";

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