/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "set"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"

const char IN [ ] =  "algola.in" ;
const char OUT [ ] = "algola.out" ;
const int MAX = 5014 ;
const int MOD = 3210121 ;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( int a = b ; a >= c ; -- a )

using namespace std ;

ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;

vector < int > gr [ MAX ] ;
vector < pair < int , int > > init [ MAX ] ;

int cap [ MAX ] [ MAX ] ;
int flow [ MAX ] [ MAX ] ;

inline void add ( int i , int j , int c )
{
    gr [ i ].pb ( j ) ;
    gr [ j ].pb ( i ) ;

    cap [ i ] [ j ] = c ;
}

queue < int > Q ;
int tata [ MAX ] ;
int DD ;

inline int flux ( )
{
    Q.push ( 0 ) ;

    FORN ( i , 0 , 5009 ) tata [ i ] = -1 ;

    Q.push ( 0 ) ;
    tata [ 0 ] = 0 ;

    while ( !Q.empty() )
    {
        int nod = Q.front() ;
        Q.pop() ;

        for ( auto x : gr [ nod ] )
            if ( tata [ x ] == -1 and cap [ nod ] [ x ] > flow [ nod ] [ x ] )
            {
                tata [ x ] = nod ;
                if ( x != DD )
                    Q.push ( x ) ;
            }
    }

    return tata [ DD ] != -1 ;
}

int main()
{
    int n , m ;
    cin >> n >> m ;

    int S = 0 ;

    FORN ( i , 1 , n )
    {
        int x ;
        cin >> x ;
        add ( 0 , i , x ) ;
        S = S + x ;
    }

    FORN ( i , 1 , m )
    {
        int x , y , c ;
        cin >> x >> y >> c ;

        init [ x ].pb ( mp ( y , c ) ) ;
        init [ y ].pb ( mp ( x , c ) ) ;
    }

    int CET = 1 ; int fluxmaxim = 0 ;
    for ( ; fluxmaxim < S ; ++ CET )
    {
        DD = n * CET + 1 ;

        FORN ( i , 1 , n )
        {
            add ( ( CET - 1 ) * n + i , CET * n + i , 1 << 30 ) ;

            for ( auto x : init [ i ] )
                add ( ( CET - 1 ) * n + i , CET * n + x.first , x.second ) ;
        }

        while ( flux ( ) )
        {
            int local = 1 << 30 ;
            for ( int i = DD ; i ; i = tata [ i ] )
                local = min ( local , cap [ tata [ i ] ] [ i ] - flow [ tata [ i ] ] [ i ] ) ;
            for ( int i = DD ; i ; i = tata [ i ] )
            {
                flow [ tata [ i ] ] [ i ] += local ;
                flow [ i ] [ tata [ i ] ] -= local ;
            }

            fluxmaxim += local ;
        }
    }

    cout << -- CET ;

    return 0;
}