#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct Edge {int x,y,c;} a[305];
int A[55];
int N,M,Oameni,D;
short C[5005][5005];
int p[5005];
vector<int> G[5005];
int BFS()
{
    for(int i=1;i<=D;i++)
        p[i]=-1;
    queue<int> Q;
    p[0]=-2;Q.push(0);
    while(!Q.empty())
    {
        int u=Q.front();
        for(vector<int>::iterator it=G[u].begin();it!=G[u].end();it++)
            if(p[*it]==-1 && C[u][*it]>0)
            {
                Q.push(*it);
                p[*it]=u;
            }
        Q.pop();
    }
    if(p[D]!=-1)
        return 1;
    return 0;
}
bool MaxFlow(int Timp)
{
    D=(Timp+1)*N+1;
    for(int i=0;i<=D;i++)
        G[i].clear();
    memset(C,0,sizeof(C));
    for(int i=1;i<=M;i++)
        for(int j=0;j<Timp;j++)
        {
            int x=a[i].x+N*j;
            int y=a[i].y+N*(j+1);
            G[x].push_back(y);
            G[y].push_back(x);
            C[x][y]=C[y][x]=a[i].c;
        }
    for(int i=1;i<=N;i++)
        for(int j=0;j<Timp;j++)
        {
            G[i+N*j].push_back(i+N*(j+1));
            G[i+N*(j+1)].push_back(i+N*j);
            C[i+N*j][i+N*(j+1)]=100;
        }
    for(int i=1;i<=N;i++)
    {
        G[0].push_back(i);
        G[i].push_back(0);
        C[0][i]=A[i];
    }
    for(int i=0;i<=Timp;i++)
    {
        G[D].push_back(N*i+1);
        G[N*i+1].push_back(D);
        C[N*i+1][D]=100;
    }
    short MaxFlow=0;
    while(BFS())
    {
        short MinFlow=C[p[D]][D];
        for(int u=p[D];u!=0;u=p[u])
            MinFlow=min(MinFlow,C[p[u]][u]);
        for(int u=D;u!=0;u=p[u])
        {
            C[p[u]][u]-=MinFlow;
            C[u][p[u]]+=MinFlow;
        }
        MaxFlow+=MinFlow;
    }
    return MaxFlow==Oameni;
}
int main()
{
    freopen("algola.in","r",stdin);
    freopen("algola.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&A[i]);
        Oameni+=A[i];
    }
    for(int i=1;i<=M;i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
    int st,dr,med,last;
    last=100;st=1;dr=100;
    while(st<=dr)
    {
        med=(st+dr)/2;
        if(MaxFlow(med))
            last=med,dr=med-1;
        else
            st=med+1;
    }
    printf("%d\n",last);
    return 0;
}