#include <cstdio>
#include <cstring>
#include <vector>

#define INF 100
#define MAXN 50
#define MAXT 100
#define MAXK 5052
#define MAXM 300

std::vector <int> v[MAXK+1];
int n, u, k, s, d, cine[MAXN+1][MAXT+1], e[MAXN+1];
int val[2*MAXM+1], next[2*MAXM+1], cost[2*MAXM+1];
int lista[MAXN+1], q[MAXK], from[MAXK+1];
char c[MAXK+1][MAXK+1], f[MAXK+1][MAXK+1];
bool viz[MAXK+1];

inline void adauga(int x, int y, int z){
    u++;
    val[u]=y;
    cost[u]=z;
    next[u]=lista[x];
    lista[x]=u;
}

inline void graf(int t){
    for(int i=1; i<=n; i++)
        for(int j=0; j<=t; j++)
            cine[i][j]=++k;
    d=++k;
    for(int i=1; i<=n; i++){
        v[s].push_back(cine[i][0]);
        v[cine[i][0]].push_back(s);
        c[s][cine[i][0]]=e[i];
        for(int j=0; j<t; j++){
            v[cine[i][j]].push_back(cine[i][j+1]);
            v[cine[i][j+1]].push_back(cine[i][j]);
            c[cine[i][j]][cine[i][j+1]]=INF;
            int p=lista[i];
            while(p){
                v[cine[i][j]].push_back(cine[val[p]][j+1]);
                v[cine[val[p]][j+1]].push_back(cine[i][j]);
                c[cine[i][j]][cine[val[p]][j+1]]+=cost[p];
                p=next[p];
            }
        }
    }
    for(int j=0; j<=t; j++){
        v[d].push_back(cine[1][j]);
        v[cine[1][j]].push_back(d);
        c[cine[1][j]][d]=INF;
    }
}

inline void reset(){
    for(int i=0; i<=k; i++){
        for(auto x:v[i])
            c[i][x]=f[i][x]=0;
        v[i].clear();
    }
    k=0;
}

inline bool bfs(){
    int st=0, dr=0, x;
    q[dr++]=s;
    memset(viz, 0, sizeof viz);
    viz[s]=1;
    while((st<dr)&&(!viz[d])){
        x=q[st++];
        for(auto y:v[x]){
            if((!viz[y])&&(c[x][y]>f[x][y])){
                viz[y]=1;
                from[y]=x;
                q[dr++]=y;
            }
        }
    }
    return viz[d];
}

inline int flux(int t){
    graf(t);

    int y, ans=0;
    char r;
    while(bfs()){
        for(auto x:v[d]){
            if((viz[x])&&(c[x][d]-f[x][d]>0)){
                from[d]=x;
                y=d;
                r=INF;
                while(y!=s){
                    if(c[from[y]][y]-f[from[y]][y]<r)
                        r=c[from[y]][y]-f[from[y]][y];
                    y=from[y];
                }
                y=d;
                while(y!=s){
                    f[from[y]][y]+=r;
                    f[y][from[y]]-=r;
                    y=from[y];
                }
                ans+=r;
            }
        }
    }

    reset();

    return ans;
}

int main(){
    FILE *fin, *fout;
    fin=fopen("algola.in", "r");
    fout=fopen("algola.out", "w");

    int m, tot=0, x, y, z;
    fscanf(fin, "%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        fscanf(fin, "%d", &e[i]);
        tot+=e[i];
    }
    for(int i=1; i<=m; i++){
        fscanf(fin, "%d%d%d", &x, &y, &z);
        adauga(x, y, z);
        adauga(y, x, z);
    }

    int st=0, dr=MAXT;
    while(st<dr){
        int mij=(st+dr)/2;
        if(flux(mij)<tot) st=mij+1;
        else dr=mij;
    }
    fprintf(fout, "%d\n", st);

    fclose(fin);
    fclose(fout);
    return 0;
}