#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

#define maxn 110
#define maxd 5520

long n, m, i, j, k, a, b, cs, t, ok, sol, l, fiu, nod;
short int nr[maxn], c[maxd][maxd], f[maxd][maxd], coa[maxd*maxd], tata[maxd], fol[maxd];
vector <long> v[maxn], w[maxn];

long flux()
{
    long rez, l1, l2;
    memset(tata, 0, sizeof(tata));
    memset(fol, 0, sizeof(fol));
    fol[0]=1;
    l=1;
    coa[1]=0;
    l1=1;
    l2=t*n+1;
    for(i=1; i<=l && !ok; i++)
    {
        nod=coa[i];
        if(nod==0)
        {
            l1=1;
            l2=t*n+1;
        }
        else
        {
            l1=(nod+n-1)/n*n+1;
            l2=l1+n-1;
            if(l2>t*n+1) l2=t*n+1;
        }
        for(j=l1; j<=l2; j++)
        {
            if(!fol[j] && c[nod][j]-f[nod][j]>0)
            {
                coa[++l]=j;
                tata[j]=nod;
                fol[j]=1;
                if(j==t*n+1)
                {
                    ok=1;
                }
            }
        }
    }
    if(!ok) return 0;
    nod=t*n+1;
    rez=5000;
    while(nod!=0)
    {
        fiu=tata[nod];
        if(rez>c[fiu][nod]-f[fiu][nod]) rez=c[fiu][nod]-f[fiu][nod];
        nod=fiu;
    }
    nod=t*n+1;
    while(nod!=0)
    {
        fiu=tata[nod];
        f[fiu][nod]+=rez;
        f[nod][fiu]-=rez;
        nod=fiu;
    }
    return rez;
}

long bs(long left, long right)
{
    long med, rez;
    rez=1;
    while(left<=right)
    {
        med=(left+right)/2;
        memset(f, 0, sizeof(f));
        for(i=1; i<=n; i++)
        {
            c[0][(t-med)*n+i]=nr[i];
        }
        ok=1;
        sol=0;
        while(ok)
        {
            ok=0;
            sol+=flux();
        }
        if(sol>=nr[0])
        {
            rez=med;
            right=med-1;
        }
        else
        {
            left=med+1;
        }
        for(i=1; i<=n; i++)
        {
            c[0][(t-med)*n+i]=0;
        }
    }
    return rez;
}  

int main()
{
    freopen("algola.in", "r", stdin);
    freopen("algola.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++)
    {
        scanf("%d", &nr[i]);
        nr[0]+=nr[i];
    }
    t=nr[0]*n;
    for(i=0; i<t-1; i++)
    {
        for(j=1; j<=n; j++)
        {
            c[j+i*n][j+(i+1)*n]=maxd;
        }
    }
    for(i=1; i<=m; i++)
    {
        scanf("%d%d%d", &a, &b, &cs);
        if(a>b) swap(a, b);
        for(j=0; j<t-1; j++)
        {
            c[a+j*n][b+(j+1)*n]+=cs;
            c[b+j*n][a+(j+1)*n]+=cs;
        }        
        if(a==1)
        {
            c[(t-1)*n+b][t*n+1]+=cs;
        }
    }
    c[(t-1)*n+1][t*n+1]=maxd;
    printf("%d\n", bs(1, t));
    return 0;
}