#include <bits/stdc++.h>
#define MaxN 5000
#define oo 100
using namespace std;

char f[MaxN+1][MaxN+1];
char c[MaxN+1][MaxN+1];
vector<int> L[MaxN+1];
vector<int> V[MaxN+1];
queue<int> Q;
int t[MaxN+1];
int N,M,S,D;

void AddEdge(int x, int y, int l)
{
    c[x][y] = l;
    L[x].push_back(y);
}

bool BFS()
{
    memset(t, 0, sizeof(t));

    Q.push(S);
    t[S] = -1;
    while(!Q.empty())
    {
        int x = Q.front();
        Q.pop();

        for(auto y : L[x])
        if(!t[y] && f[x][y] < c[x][y])
        {
            t[y] = x;
            Q.push(y);
        }
    }

    return t[D];
}

int GetFlow()
{
    int i,flow,add;

    for(flow = 0; BFS(); )
        for(auto x : L[D])
        if(t[x])
        {
            add = c[x][D] - f[x][D];
            for(i = x; t[i] > 0; i = t[i]) add = min(add, c[ t[i] ][i] - f[ t[i] ][i]);
            if(!add) continue;

            flow += add;
            f[x][D] += add;
            f[D][x] -= add;
            for(i = x; t[i] > 0; i = t[i])
            {
                f[ t[i] ][i] += add;
                f[i][ t[i] ] -= add;
            }
        }

    return flow;
}

int main(){
    FILE* fin = fopen("algola.in","r");
    FILE* fout = fopen("algola.out","w");

    int i,T,x,y,l,flux,total=0;

    fscanf(fin,"%d %d",&N,&M);
    D = MaxN; S = D - 1;

    for(i = 1; i <= N; ++i)
    {
        fscanf(fin,"%d",&x);
        AddEdge(S, i, x);
        total += x;
    }

    for(i = 1; i <= M; ++i)
    {
        fscanf(fin,"%d %d %d",&x,&y,&l);
        c[x][y] = c[y][x] = l;
        V[x].push_back(y);
        V[y].push_back(x);
    }

    AddEdge(1, D, oo);
    AddEdge(D, 1, oo);
    flux = GetFlow();
    for(T = 0; flux < total; )
    {
        ++T;
        AddEdge(N * T + 1, D, oo);
        AddEdge(D, N * T + 1, oo);
        for(i = 1; i <= N; ++i)
        {
            for(auto j : V[i]) AddEdge(N * (T-1) + i, N * T + j, c[i][j]);
            AddEdge(N * (T-1) + i, N * T + i, oo);
        }

        flux += GetFlow();
    }

    fprintf(fout,"%d\n",T);


return 0;
}