#include<stdio.h>
#include<vector>

#define inf (1<<29)
#define maxn 53
#define pb push_back
#define mp make_pair

using namespace std;

FILE*f=fopen("algola.in","r");
FILE*g=fopen("algola.out","w");

int n,m;
int cp[maxn][maxn],S,D,T[maxn<<1][maxn],F[maxn<<1][maxn][maxn],prev[maxn<<1][maxn],viz[maxn<<1][maxn],C[2][maxn*maxn<<1];
vector<int>W[maxn];
vector< pair<int,int> >G[maxn<<1][maxn];

inline int min ( const int &a , const int &b ){
	return a <= b ? a : b;
}

inline int max ( const int &a , const int &b ){
	if ( b == 101 )	return a;
	if ( a == 101 )	return b;
	return a >= b ? a : b;
}

inline void build_network ( int timp ) {
    
	for ( int t = 0 ; t <= timp ; ++t ){
		for ( int i = 1 ; i <= n+1 ; ++i ){
			G[t][i].clear();
			for ( int j = 1 ; j <= n+1 ; ++j ){
				F[t][i][j] = 0;
			}
		}
	}
	
    for ( int t = 0 ; t < timp ; ++t ){
		for ( int i = 1 ; i <= n ; ++i ){
			
			for ( int j = 0 ; j < W[i].size() ; ++j ){
				int vcn = W[i][j];
				G[t][i].pb(mp(t+1,vcn));
				G[t+1][vcn].pb(mp(t,i));
			}
		}
	}
	
	for ( int i = 1 ; i <= n ; ++i ){
		G[101][S].pb(mp(0,i));
	}
}

inline bool BFS ( int timp ) {
    
    for ( int i = 0 ; i <= timp ; ++i ){
        for ( int j = 1 ; j <= n+1 ; ++j ){
            viz[i][j] = 0;
        }
    }
    
    int p = 1,u = 0,ok = 0;
    ++u; C[0][u] = S; C[1][u] = 101;
    
    while ( p <= u ){
        int nod = C[0][p],moment = C[1][p];
        
        for ( int i = 0 ; i < G[moment][nod].size() ; ++i ){
            int nodvcn = G[moment][nod][i].second; int nextm = G[moment][nod][i].first;
            
			if ( !viz[nextm][nodvcn] && cp[nod][nodvcn] > F[max(moment,nextm)][nod][nodvcn] ){
                
                if ( nodvcn == D && nextm == timp ){
                    ok = 1; continue ;
                }
                
                ++u; C[0][u] = nodvcn; C[1][u] = nextm; viz[nextm][nodvcn] = 1;
                T[nextm][nodvcn] = nod; prev[nextm][nodvcn] = moment;
            }
        }
        
        ++p;
    }
    
    return ok;
}

inline int flux ( int timp ){
    int flow = 0;
    
    while ( BFS(timp) ){
        
        for ( int i = 0 ; i < W[D].size() ; ++i ){
            T[timp][D] = W[D][i];
            
            int minim = inf,moment = timp,nod; prev[moment][D] = moment-1;
            for ( nod = D ; T[moment][nod] ; ){
				int next = T[moment][nod],prevmoment = prev[moment][nod];
				minim = min(minim,cp[nod][next]-F[max(moment,prevmoment)][next][nod]);
				nod = next; moment = prevmoment;
            }
            if ( nod != S )	continue ;
			
            moment = timp;
            for ( nod = D ; T[moment][nod] ; ){
                int next = T[moment][nod],prevmoment = prev[moment][nod];
				F[max(moment,prevmoment)][next][nod] += minim;
				F[max(moment,prevmoment)][nod][next] -= minim;
				nod = next; moment = prevmoment;
            }
            
            flow += minim;
        }
    }
    
    return flow;
}

int main () {
    
    fscanf(f,"%d %d",&n,&m); S = n+1; D = 1;
    int x,y,c,max_flow = 0;
    for ( int i = 1 ; i <= n ; ++i ){
        fscanf(f,"%d",&x); max_flow += x;
        cp[S][i] = cp[i][S] = x; 
		W[S].pb(i);
        cp[i][i] = inf; W[i].pb(i);
    }
    for ( int i = 1 ; i <= m ; ++i ){
        fscanf(f,"%d %d %d",&x,&y,&c);
        W[x].pb(y);	W[y].pb(x);
        cp[x][y] += c; cp[y][x] += c;
    }
    
    int p = 0,middle,u = (n<<1);
    while ( p <= u ){
        middle = (p + u) >> 1;
        
		build_network(middle);
        if ( flux(middle) >= max_flow ){
            u = middle-1;
        }
        else{
            p = middle+1;
        }
    }
    
    fprintf(g,"%d\n",p);
    
    fclose(f);
    fclose(g);
    
    return 0;
}