#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
ifstream f("algola.in");
ofstream g("algola.out");
int N,M,sum,MaxFlow;
vector <int> G[5505];
queue <int> Q;
vector <pair<int,int> >GG[5505];
bool Use[5505];
int C[5505][5505],TT[5505],F[5505][5505];
int nodes;
void Read()
{
    f>>N>>M;
    for(int i=1;i<=N;i++)
        f>>C[0][i],sum+=C[0][i];
    for(int i=1;i<=M;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        GG[x].push_back(make_pair(y,c));
        GG[y].push_back(make_pair(x,c));
    }
    for(int i=1;i<=N;i++)
    {
        G[0].push_back(i);
        G[i].push_back(0);
    }
 
    GG[1].push_back(make_pair(N+1,0x3f3f3f3f));
    GG[N+1].push_back(make_pair(1,0x3f3f3f3f));
    nodes=N+1;
}
 
void buildG(int T)
{
    int cnt=1;
    for(cnt=1;cnt<=N+1;cnt++)
    {
        ++nodes;
        for(int i=0;i<GG[cnt].size();i++)
        {
            int neighb=GG[cnt][i].first,c=GG[cnt][i].second;
            if(neighb==0)
                continue;
            if(neighb!=N+1)
            {
                 G[nodes-N-1].push_back(neighb+T*(N+1));
                G[neighb+T*(N+1)].push_back(nodes-N-1);
                C[nodes-N-1][neighb+T*(N+1)]+=c;
            }
            else
            {
                G[nodes].push_back(N+1);
                G[N+1].push_back(nodes);
                C[nodes][N+1]=0x3f3f3f3f;
            }
 
        }
        if(cnt!=N+1)
        {
            G[nodes-N-1].push_back(nodes);
            G[nodes].push_back(nodes-N-1);
            C[nodes-N-1][nodes]=0x3f3f3f3f;
        }
        else
        {
            G[nodes].push_back(N+1);
            G[N+1].push_back(nodes);
            C[nodes][N+1]=0x3f3f3f3f;
        }
    }
}
int BFS()
{
    memset(Use,0,sizeof(Use));
    Q.push(0);Use[0]=1;
    while(!Q.empty())
    {
        int Node = Q. front(); Q. pop();
 
        if(Node == N+1) continue;
        for(int i=0;i<G[Node].size();i++)
        {
            int Neighbour = G[Node][i];
            if(Use[Neighbour]==1)
                continue;
            if(C[Node][Neighbour]-F[Node][Neighbour]>0)
            {
                TT[Neighbour] = Node;
                Q.push(Neighbour);
                Use[Neighbour] = 1;
            }
        }
 
    }
return Use[N+1];
 
}
 
int Solve()
{
    while(BFS())
    {
 
        for(unsigned int k = 0; k<G[N+1].size(); ++k)
        {
 
        int Vecin = G[N+1][k];
 
        if(!Use[Vecin] || C[Vecin][N+1]-F[Vecin][N+1] == 0) continue;
 
        TT[N+1] = Vecin;
 
        int Fmin = 0x3f3f3f3f;
 
        for(int i = N+1 ; i != 0 ; i = TT[i])
            Fmin = min(Fmin,C[TT[i]][i]-F[TT[i]][i]);
 
        MaxFlow += Fmin;
 
        for(int i = N+1 ; i != 0 ; i = TT[i])
        {
            F[TT[i]][i] += Fmin;
            F[i][TT[i]] -= Fmin;
        }
 
        }
    }
    return MaxFlow;
}
 
int main()
{
    Read();
    int T=0;
    while(Solve()<sum)
    {
        ++T;
        buildG(T);
    }
    g<<T<<"\n";
    return 0;
}