#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

const int INF = (1 << 30);
const int NMAX = 155;
const int MMAX = 305;
struct Edge
{
    int u, v, cap, flow;
};

int N, M, T, a[NMAX];
vector < pair <int, int> > graph[NMAX * NMAX];
vector <Edge> edges;
vector < pair <int, int> > adj[NMAX];
int source = 0, sink;
int all, indEdge;
int level[NMAX * NMAX], last[NMAX * NMAX];

void AddEdge(int u, int v, int cap)
{
    edges.push_back({ u, v, cap, 0 });
    graph[u].push_back(make_pair(v, indEdge));
    ++indEdge;
    edges.push_back({ v, u, 0, 0 });
    graph[v].push_back(make_pair(u, indEdge));
    ++indEdge;
}

bool bfs()
{
    for (int i = 0; i <= (T + 1) * N; ++i)
        level[i] = INF;
    level[source] = 0;
    queue <int> q;
    q.push(source);
    while (!q.empty())
    {
        int node = q.front();
        q.pop();
        for (auto& x : graph[node])
        {
            int nnode = x.first, flow = edges[x.second].flow, cap = edges[x.second].cap;
            if (level[nnode] > level[node] + 1 && flow < cap)
            {
                level[nnode] = level[node] + 1;
                q.push(nnode);
            }
        }
    }
    return (level[sink] != INF);
}

int dfs(int node, int deltaflow)
{
    if (node == sink)
        return deltaflow;
    else
    {
        for (int& p = last[node]; p < graph[node].size(); ++p)
        {
            int nnode = graph[node][p].first;
            int ind = graph[node][p].second;
            int flow = edges[ind].flow;
            int cap = edges[ind].cap;
            if (level[nnode] == level[node] + 1 && flow < cap)
            {
                int currflow = dfs(nnode, min(deltaflow, cap - flow));
                if (currflow > 0)
                {
                    edges[ind].flow += currflow;
                    edges[ind ^ 1].flow -= currflow;
                    return currflow;
                }
            }
        }
        return 0;
    }
}

int Dinic()
{
    int deltaflow, maxflow = 0;
    while (bfs())
    {
        for (int i = 0; i <= (T + 1) * N; ++i)
            last[i] = 0;
        deltaflow = dfs(source, INF);
        while (deltaflow != 0)
        {
            maxflow += deltaflow;
            deltaflow = dfs(source, INF);
        }
    }
    return maxflow;
}

int main()
{
    ifstream fin("algola.in");
    ofstream fout("algola.out");
    fin >> N >> M;
    for (int i = 1; i <= N; ++i)
    {
        fin >> a[i];
        all += a[i];
    }
    for (int i = 1; i <= M; ++i)
    {
        int u, v, cap;
        fin >> u >> v >> cap;
        adj[u].push_back(make_pair(v, cap));
        adj[v].push_back(make_pair(u, cap));
    }
    int sum = 0;
    T = 1;
    while (sum != all)
    {
        sink = T * N + 1;
        for (int i = (T - 1) * N + 1; i <= T * N; ++i)
        {
            int node = i - (T - 1) * N;
            AddEdge(0, i, a[node]);
            for (auto& j : adj[node])
                AddEdge(i, j.first + T * N, j.second);
            AddEdge(node, node + N, INF);
        }
        sum += Dinic();
        for (auto& j : graph[0])
        {
            if ((T - 1) * N + 1 <= j.first && j.first <= T * N)
            {
                int node = j.first - (T - 1) * N;
                int flow = edges[j.second].flow;
                a[node] -= flow;
            }
        }
        ++T;
    }
    fout << T - 1 << "\n";
    fin.close();
    fout.close();
    return 0;
}