#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;
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;
};
void addEdge(int src,int dest,int cost,bool rev=false) {
    if (rev==true) {
        v[src].emplace_back(dest,cost,v[dest].size());
        v[dest].emplace_back(src,cost,v[src].size()-1);
    }else {
        v[src].emplace_back(dest,cost,v[dest].size());
        v[dest].emplace_back(src,0,v[src].size()-1);
    }

}
vector<cst> costuri;
int main() {
    int n,m;
    f>>n>>m;
    int cost[400];
    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<=52;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-1;j++) {
                addEdge(x+j*n,y+(j+1)*n,cost,false);
                addEdge(y+j*n,x+(j+1)*n,cost,false);
            }
        }
        for (int j=0;j<ans-1;j++) {
            for (int i=1;i<=n;i++) {
                addEdge(i+j*n,i+(j+1)*n,10000000,false);
            }
        }
        src=0;
        dest=(ans-1)*n+1;
        for (int i=1;i<=n;i++) {
            addEdge(src,i,cost[i],false);
        }
        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;
        }
    }

}