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

using namespace std;

#define maxn 110
#define maxd 5520
#define maxm 51000
#define pb push_back

struct muchie
{
    long a;
    long b;
    long c;
    long f;
    long mi;
};
long n, m, nm, minv, i, j, k, a, b, cs, t, ok, sol, l, fiu, nod;
short int nr[maxn];
muchie muc[maxm];
short int coa[maxd*maxd], tata[maxd];
short int fol[maxd];
vector <long> v[maxd];

long flux()
{
    long rez, l1, l2;
    memset(tata, 0, sizeof(tata));
    memset(fol, 0, sizeof(fol));
    fol[0]=1;
    l=1;
    coa[1]=0;
    for(i=1; i<=l && !ok; i++)
    {
        nod=coa[i];
        for(k=0; k<v[nod].size(); k++)
        {
            j=v[nod][k];
            fiu=muc[j].b;
            if(muc[j].a==nod && !fol[fiu] && muc[j].c-muc[j].f>0)
            {
                coa[++l]=fiu;
                tata[fiu]=j;
                fol[fiu]=1;
                if(fiu==t*n+1)
                {
                    ok=1;
                }
            }
        }
    }
    if(!ok) return 0;
    nod=t*n+1;
    rez=10000;
    while(nod!=0)
    {
        fiu=tata[nod];
        if(rez>muc[fiu].c-muc[fiu].f) rez=muc[fiu].c-muc[fiu].f;
        nod=muc[fiu].a;
    }
    nod=t*n+1;
    while(nod!=0)
    {
        fiu=tata[nod];
        minv=muc[fiu].mi;
        muc[fiu].f+=rez;
        muc[minv].f-=rez;
        nod=muc[fiu].a;
    }
    return rez;
}

long bs(long left, long right)
{
    long med, rez;
    rez=1;
    while(left<=right)
    {
        med=(left+right)/2;
        for(nod=1, i=nm-2*n+1; i<nm; i+=2, nod++)
        {
            muc[i].b=nod+(t-med)*n;
            v[0].pb(i);
            muc[i+1].a=nod+(t-med)*n;
            v[muc[i+1].a].pb(i+1);
        }
        for(i=1; i<=nm; i++)
        {
            muc[i].f=0;
        }
        ok=1;
        sol=0;
        while(ok)
        {
            ok=0;
            sol+=flux();
        }
        if(sol>=nr[0])
        {
            rez=med;
            right=med-1;
        }
        else
        {
            left=med+1;
        }
        v[0].clear();
        for(nod=1, i=nm-2*n+1; i<nm; i+=2, nod++)
        {
            v[muc[i+1].a].pop_back();
        }
    }
    return rez;
}  

void muchie(long a, long b, long c1, long c2)
{
    muc[++nm].a=a;
    if(a!=0) v[a].pb(nm);
    muc[nm].b=b;
    muc[nm].c=c1;
    muc[nm].f=0;
    muc[nm].mi=nm+1;
    muc[++nm].a=b;
    if(a!=0) v[b].pb(nm);
    muc[nm].b=a;
    muc[nm].c=c2;
    muc[nm].f=0;
    muc[nm].mi=nm-1;
}

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=100;
    for(i=0; i<t-1; i++)
    {
        for(j=1; j<=n; j++)
        {
            muchie(j+i*n, j+(i+1)*n, 510, 0);
        }
    }
    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++)
        {
            muchie(a+j*n, b+(j+1)*n, cs, 0);
            muchie(b+j*n, a+(j+1)*n, cs, 0);
        }        
        if(a==1)
        {
            muchie((t-1)*n+b, t*n+1, cs, 0);
        }
    }
    muchie((t-1)*n+1, t*n+1, 510, 0);
    for(i=1; i<=n; i++)
    {
        muchie(0, 0, nr[i], 0);
    }
    printf("%d\n", bs(1, t));
    return 0;
}