#include<fstream>
#include<vector>
#include<deque>
#include<bitset>
#define f first
#define s second
#define inf 100
using namespace std;
int n, m, i, x, y, ti, j, sum, minim, p, sol, source, dest, z, vecin;
int t[5005];
char c[5005][5005], fl[5005][5005];
vector<int> v[5005];
vector<pair<int, int> > w[5005];
deque<int> cd;
bitset<5005> viz;
ifstream fin("algola.in");
ofstream fout("algola.out");
int bfs(){
    viz.reset();
    viz[source] = 1;
    t[0] = -1;
    cd.push_back(source);
    while(!cd.empty()){
        int nod = cd.front();
        for(int i = 0; i < v[nod].size(); i++){
            int vecin = v[nod][i];
            if(fl[nod][vecin] < c[nod][vecin] && viz[vecin] == 0){
                viz[vecin] = 1;
                t[vecin] = nod;
                cd.push_back(vecin);
            }
        }
        cd.pop_front();
    }
    if(viz[dest] == 1){
        return 1;
    }
    else{
        return 0;
    }
}
void adauga(int x, int y, int cp){
    v[x].push_back(y);
    v[y].push_back(x);
    c[x][y] = cp;
}
int main(){
    fin>> n >> m;
    source = 0;
    dest = 100 * n + 1;
    for(i = 1; i <= n; i++){
        fin>> x;
        sum += x;
        adauga(source, i, x);
    }
    adauga(1, dest, inf);
    for(i = 1; i <= m; i++){
        fin>> x >> y >> z;
        w[x].push_back(make_pair(y, z));
        w[y].push_back(make_pair(x, z));
    }
    while(sol < sum){
        ti++;
        for(i = 1; i <= n; i++){
            x = ti * n + i;
            adauga(x - n, x, inf);
            for(j = 0; j < w[i].size(); j++){
                adauga(x, ti * n + w[i][j].f, w[i][j].s);
            }
        }
        adauga(ti * n + 1, dest, inf);
        while(bfs()){
            for(i = 0; i < v[dest].size(); i++){
                vecin = v[dest][i];
                if(viz[vecin] == 0 || fl[vecin][dest] == c[vecin][dest]){
                    continue;
                }
                minim = c[vecin][dest] - fl[vecin][dest];
                p = vecin;
                while(t[p] >= 0){
                    minim = min(minim, c[ t[p] ][p] - fl[ t[p] ][p]);
                    p = t[p];
                }
                sol += minim;
                fl[vecin][dest] += minim;
                fl[dest][vecin] -= minim;
                p = vecin;
                while(t[p] >= 0){
                    fl[ t[p] ][p] += minim;
                    fl[p][ t[p] ] -= minim;
                    p = t[p];
                }
            }
        }
    }
    fout<< ti <<"\n";
    return 0;
}