#include <bits/stdc++.h>

using namespace std;
ifstream f("cuplaj.in");
ofstream g("cuplaj.out");

struct vecini {
    int node;
    int cap;
    int rev;
};
vector<vecini> v[20008];
int depth[20008];
int nrNodes,m;
int src;
int dest;
void BFS() {
    queue<int> q;
    q.push(src);
    for (int i=1;i<=nrNodes;i++) {
        depth[i]=-1;
    }
    depth[src]=0;
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        for(auto nod:v[x]) {
            if (nod.node==dest) {
                continue;
            }
            if (nod.cap!=0) {
                if (depth[nod.node]==-1) {
                    depth[nod.node]=depth[x]+1;
                    q.push(nod.node);
                }
            }
        }
    }
}

int DFS(int node,int possible=1000000) {
    int ans=0;
    for (auto& vec:v[node]) {
        if (vec.cap==0) {
            continue;
        }
        if (vec.node==dest) {
            int flow=min(possible,vec.cap);
            ans+=flow;
            possible-=flow;
            vec.cap-=flow;
        }
        if (depth[vec.node]==depth[node]+1) {
            int flow=DFS(vec.node,min(possible,vec.cap));
            ans+=flow;
            possible-=flow;
            vec.cap-=flow;
            v[vec.node][ vec.rev].cap+=flow;
        }
    }
    return ans;
}
struct cst {
    int x,y,cost;

};
vector<cst> costuri;
int main() {
    int n,m;
    f>>n>>m;
    int cost[51];
    int costTotal=0;
    for(int i=1;i<=n;i++) {
        f>>cost[i];
        costTotal+=cost[i];
    }

    for(int i=0;i<m;i++) {
        int x,y,cost;
        f>>x>>y>>cost;
        costuri.push_back({x,y,cost});
    }
    for (int ans=1;ans<=10000;ans++) {
        nrNodes=ans*n+10;
        for (int i=0;i<20000;i++) {
            v[i].clear();
        }
        for (auto [x,y,cost]:costuri) {
            for (int j=0;j<ans;j++) {
                v[x+j*n].emplace_back(y+(j+1)*n,cost,(int)v[y+(j+1)*n].size());
                v[y+(j+1)*n].emplace_back(x+j*n,0,(int)v[x+j*n].size()-1);


                v[y+j*n].emplace_back(x+(j+1)*n,cost,(int)v[x+(j+1)*n].size());
                v[x+(j+1)*n].emplace_back(y+j*n,0,(int)v[y+j*n].size()-1);
            }
        }
        for (int j=0;j<ans;j++) {
            for (int i=1;i<=n;i++) {
                v[i+j*n].emplace_back(i+(j+1)*n,1200000,(int)v[i+(j+1)*n].size());
                v[i+(j+1)*n].emplace_back(i+j*n,1200000,(int)v[i+j*n].size()-1);
            }
        }
        src=0;
        dest=2;
        for (int i=1;i<=n;i++) {
            v[src].emplace_back(i,cost[i],v[i].size());
            v[i].emplace_back(src,0,v[i].size()-1);


        }
        int rasp=0;
        while(1) {
            BFS();
            int x=DFS(src,10000000);
            if (x==0) {
                break;
            }
            rasp+=x;
        }
        if (rasp==costTotal) {
            g<<ans-1<<endl;
            return 0;
        }
    }

}