#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define maxn 55
#define maxt 101
#define inf 9999999
#define pii pair<int, int>
#define mkp make_pair

int N, M, S, D, NR, sum, sol;
int V[maxn], viz[maxn * maxt], C[30 * maxn * maxt], C2[30 * maxn * maxt], TT[maxn * maxt];
vector<int> G[maxn * maxt];
struct Muchii {
    int x, y;
} much[30 * maxn * maxt];

int BFS() {
    memset(viz, 0, sizeof(viz));
    memset(TT, 0, sizeof(TT));
    queue<int> Q;

    Q.push(S); viz[S] = 1;
    while(!Q.empty()) {
         int nod = Q.front(); Q.pop();
         for(vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++) {
              if(!viz[ much[(*it)].y ] && C[(*it)] > 0) {
                   viz[ much[(*it)].y ] = 1;
                   TT[ much[(*it)].y ] = (*it);
                   Q.push( much[(*it)].y );
                   if(much[(*it)].y == D) return 1;
              }
         }
    }

    return 0;
}

int max_flow() {
    int flow = 0;

    while(BFS()) {
         int fmin = inf;
         for(int i=D; i!=S; i=much[ TT[i] ].x) {
              fmin = min(fmin, C[ TT[i] ]);
         }
         for(int i=D; i!=S; i=much[ TT[i] ].x) {
              C[ TT[i] ] -= fmin;
              //daca am scazut pe o muchie normala tre sa adaug pe muchia ei de intoarcere
              //sau invers
              if(TT[i] % 2 == 1) {
                   C[ TT[i] + 1 ] += fmin;
              }
              else {
                   C[ TT[i] - 1 ] += fmin;
              }
         }

         flow += fmin;
    }

    return flow;
}

int check(int T) {
    for(int i=1; i<=NR; i++) {
         C[i] = C2[i];
    }

    for(int i=1; i<=N; i++) {
         much[2*i - 1].y = T * N + i;
         much[2*i].x = T * N + i;
         G[ much[2*i].x ].push_back(2*i);
    }

    int flow = max_flow();

    for(int i=1; i<=N; i++) {
         G[ much[2*i].x ].pop_back();
    }

    return flow;
}

int main() {
    FILE *f1=fopen("algola.in", "r"), *f2=fopen("algola.out", "w");
    int i, j, p, q;

    fscanf(f1, "%d %d\n", &N, &M);

    S = 0, D = N + 1;

    for(i=1; i<=N; i++) {
         fscanf(f1, "%d", &V[i]);
         sum = sum + V[i];

         NR ++; C[NR] = V[i];
         much[NR].x = S; //capatul celalalt al muchiei va fi stabilit in cautarea binara
         G[S].push_back(NR);

         NR ++; C[NR] = 0;
         much[NR].y = S; //capatul celalalt al muchiei va fi stabilit in cautarea binara
    }

    for(i=1; i<=M; i++) {
         fscanf(f1, "%d %d %d\n", &p, &q, &j);

         for(int timp = 1; timp < maxt; timp++) {
              //muchie de la (p, timp) la (q, timp - 1)
              //si invers
              NR ++; C[NR] = j;
              much[NR].x = timp * N + p;
              much[NR].y = (timp - 1) * N + q;
              G[ much[NR].x ].push_back(NR);

              NR ++; C[NR] = 0;
              much[NR].x = (timp - 1) * N + q;
              much[NR].y = timp * N + p;
              G[ much[NR].x ].push_back(NR);

              NR ++; C[NR] = j;
              much[NR].x = timp * N + q;
              much[NR].y = (timp - 1) * N + p;
              G[ much[NR].x ].push_back(NR);

              NR ++; C[NR] = 0;
              much[NR].x = (timp - 1) * N + p;
              much[NR].y = timp * N + q;
              G[ much[NR].x ].push_back(NR);
         }
    }

    for(i=1; i<=N; i++) {
         for(int timp = 1; timp < maxt; timp++) {
              //trag muchie intre acelasi nod, dar timpi diferiti
              NR ++; C[NR] = inf;
              much[NR].x = timp * N + i;
              much[NR].y = (timp - 1) * N + i;
              G[ much[NR].x ].push_back(NR);

              NR ++; C[NR] = 0;
              much[NR].x = (timp - 1) * N + i;
              much[NR].y = timp * N + i;
              G[ much[NR].x ].push_back(NR);
         }
    }

    for(i=1; i<=NR; i++) {
         C2[i] = C[i];
    }

    int ls = 0, ld = maxt;
    while(ls <= ld) {
         int mij = (ls + ld) >> 1;

         if(check(mij) == sum) {
              sol = mij;
              ld = mij - 1;
         }
         else {
              ls = mij + 1;
         }
    }

    fprintf(f2, "%d\n", sol - 1);
    fclose(f1); fclose(f2);
    return 0;
}