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

using namespace std;

#define maxn 110
#define maxd 5520
#define maxm 510000

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

int flux()
{
    int rez, l1, l2;
    memset(tata, 0, sizeof(tata));
    memset(fol, 0, sizeof(fol));
    fol[0]=1;
    l=1;
    q[1]=0;
    for(int i=1; i<=l && !ok; ++i)
    {
        nod=q[i];
        for(int k=0; k<v[nod].size(); ++k)
        {
            int j=v[nod][k];
            fiu=muc[j].b;
            if(muc[j].a==nod && !fol[fiu] && muc[j].c-muc[j].f>0)
            {
                q[++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;
}

int bs(int left, int right)
{
    int med, rez;
    rez=1;
    while(left<=right)
    {
        med=(left+right)/2;
        for(int nod=1, i=nm-2*n+1; i<nm; i+=2, ++nod)
        {
            muc[i].b=nod+(t-med)*n;
            v[0].push_back(i);
            muc[i+1].a=nod+(t-med)*n;
            v[muc[i+1].a].push_back(i+1);
        }

        for(int 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(int nod=1, i=nm-2*n+1; i<nm; i+=2, ++nod)
            v[muc[i+1].a].pop_back();
    }
    return rez;
}

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

    muc[++nm].a=b; muc[nm].b=a; muc[nm].c=c2; muc[nm].f=0;
    muc[nm].mi=nm-1;
    if(a!=0)
        v[b].push_back(nm);
}

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", &nr[i]);
        nr[0]+=nr[i];
    }

    t=100;
    for(int i=0; i<t-1; ++i)
        for(int j=1; j<=n; ++j)
            muchie(j+i*n, j+(i+1)*n, 510, 0);

    for(int i=1; i<=m; ++i)
    {
        scanf("%d%d%d", &a, &b, &cs);
        if(a>b)
            swap(a, b);
        for(int 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(int i=1; i<=n; ++i)
        muchie(0, 0, nr[i], 0);

    printf("%d\n", bs(1, t));
    return 0;
}