#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=2*2555;
vector<int> v[nmax];
char fl[nmax][nmax],c[nmax][nmax];
int q[nmax],prec[nmax];
int n,m,i,j,source,sink,timp,t,p,u,start,nod,x,sum,a,b,cap,flow,minfl;
int e(int loc,int timp)
{
return (loc-1)*101+timp+1;
}
void add(int x,int y,int cap)
{
c[x][y]=cap;
v[x].push_back(y);
v[y].push_back(x);
}
bool bfs()
{
for(i=1;i<=sink;i++)
prec[i]=0;
prec[source]=-1;
q[p=u=1]=source;
while(p<=u)
{
start=q[p];p++;
for(i=0;i<v[start].size();i++)
{
nod=v[start][i];
if((!prec[nod])&&fl[start][nod]<c[start][nod])
{
prec[nod]=start;
q[++u]=nod;
if(nod==sink)
return 1;
}
}
}
return 0;
}
int main()
{
ifstream f("algola.in");
ofstream g("algola.out");
f>>n>>m;
source=e(n,50)+1;
sink=source+1;
for(i=1;i<=n;i++)
{
f>>x;
add(source,e(i,0),x);
sum+=x;
}
for(i=1;i<=m;i++)
{
f>>a>>b>>cap;
for(t=0;t<50;t++)
{
add(e(a,t),e(b,t+1),cap);
add(e(b,t),e(a,t+1),cap);
}
}
for(i=1;i<=n;i++)
for(t=0;t<50;t++)
add(e(i,t),e(i,t+1),50);
add(e(1,0),sink,50);
while(flow<sum)
{
while(bfs())
{
nod=sink;minfl=51;
while(nod!=source)
{
minfl=min(minfl,c[prec[nod]][nod]-fl[prec[nod]][nod]);
nod=prec[nod];
}
nod=sink;
while(nod!=source)
{
fl[prec[nod]][nod]+=minfl;
fl[nod][prec[nod]]-=minfl;
nod=prec[nod];
}
flow+=minfl;
}
timp++;
add(e(1,timp),sink,50);
}
g<<timp-1;
return 0;
}