#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

int N, M, Gata, x[309], y[309], z[309], cod[109][53], A[59], lin[5009], col[5009];

class graph
{
    public:
    int flux, N, S, D, t[5009];
    char f[5009][5009], c[5009][5009];
    vector < int > muchii[5009];

    void Add_edge (int i, int j, int cost)
    {
        muchii[i].push_back(j);
        muchii[j].push_back(i);
        c[i][j] = cost;
    }

    bool bfs()
    {
        queue < int > q;
        for (int i=1; i<=D; i++)
            t[i] = -1;
        q.push(S);
        t[S] = 0;
        while (!q.empty())
        {
            int nod = q.front();
            q.pop();
            for (vector < int > :: iterator it = muchii[nod].begin(); it != muchii[nod].end(); it++)
                if (t[*it] == -1 && f[nod][*it] < c[nod][*it] && *it <= D)
                {
                    t[*it] = nod;
                    if (*it == D) return 1;
                    q.push(*it);
                }
        }
        return 0;
    }

    void calc_flux()
    {
        //flux = 0;
        while ( bfs() )
        {
            for (vector < int > :: iterator it = muchii[D].begin(); it != muchii[D].end(); it++)
                if (t[*it] != -1 && f[*it][D] < c[*it][D])
                {
                    int nod = *it, fmin = 100000;
                    t[D] = nod;
                    for (int i = D; i != S; i = t[i])
                        if (c[t[i]][i] - f[t[i]][i] < fmin)
                            fmin = c[t[i]][i] - f[t[i]][i];
                    flux += fmin;
                    for (int i = D; i != S; i = t[i])
                    {
                        f[t[i]][i] += fmin;
                        f[i][t[i]] -= fmin;
                    }
                }
        }
    }

    void Clear()
    {
        for (int i=1; i<=D; i++)
            for (vector < int > :: iterator it = muchii[i].begin(); it != muchii[i].end(); it++)
                f[i][*it] = 0;
    }
}graf;

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]);
    Gata += A[i];
}
for (int i=1; i<=M; i++)
    scanf ("%d %d %d", &x[i], &y[i], &z[i]);
graf.S = 1;
graf.N = 1;
for (int i=1; i<=100; i++)
    for (int j=1; j<=N; j++)
    {
        cod[i][j] = ++graf.N;
        lin[graf.N] = i;
        col[graf.N] = j;
    }
for (int i=1; i<=N; i++)
    graf.Add_edge (graf.S, cod[1][i], A[i]);
for (int i=1; i<100; i++)
{
    for (int j=1; j<=M; j++)
    {
        graf.Add_edge (cod[i][x[j]], cod[i+1][y[j]], z[j]);
        graf.Add_edge (cod[i][y[j]], cod[i+1][x[j]], z[j]);
    }
    for (int j=1; j<=N; j++)
        graf.Add_edge (cod[i][j], cod[i+1][j], 100);
    graf.D = cod[i+1][1];
    //graf.Clear();
    graf.calc_flux();
    /*for (int j=1; j<=graf.D; j++)
    {
        for (vector < int > :: iterator it = graf.muchii[j].begin(); it != graf.muchii[j].end(); it++)
            if (graf.c[j][*it] > 0)
                printf ("(%d %d,  %d %d) -> %d / %d\n", lin[j], col[j], lin[*it], col[*it], graf.f[j][*it], graf.c[j][*it]);
    }
    printf ("\n\n");*/
    if (graf.flux == Gata)
    {
        printf ("%d\n", i);
        return 0;
    }
}
return 0;
}