#include <bits/stdc++.h>

using namespace std;

vector<map<int, int>> G;
vector<bool> Vis;


int DFS(int node, int dest, int flow) {
    if (node == dest) return flow;
    if (Vis[node] or flow == 0) return 0;

    Vis[node] = true;
    
    for (auto p : G[node]) {
        int vec, cap; 
        tie(vec, cap) = p;

        int now = DFS(vec, dest, min(flow, cap));
        if (now > 0) {
            G[node][vec] -= now;
            G[vec][node] += now;
            return now;
        }
    }
    return 0;
}

int main() {
    ifstream cin("algola.in");
    ofstream cout("algola.out");

    int n, m; cin >> n >> m;
    vector<tuple<int, int, int>> edges(m);    
    G.resize(2 + n);
    int tot = 0;

    for (int i = 0; i < n; ++i) {
        int pop; cin >> pop;
        tot += pop;
        G[0][i + 2] = pop;
    }

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        --a; --b;

        edges[i] = make_tuple(a, b, c);
    }

    int offset = 2;
    G[offset][1] = 1e9;

    int flow = 0;
    while (flow < tot) {
        Vis.assign(G.size(), false);
        int incr = DFS(0, 1, 1e9);
        flow += incr;
        if (incr == 0) {
            int noffset = G.size();
            G.resize(noffset + n);
            G[noffset][1] = 1e9;
            for (auto p : edges) {
                int a, b, c; tie(a, b, c) = p;
                G[offset + a][noffset + b] += c;
                G[offset + b][noffset + a] += c;
            }
            for (int i = 0; i < n; ++i) {
                G[offset + i][noffset + i] = 1e9;
            }
            offset = noffset;
        }
    }
    cout << (offset - 2) / n << endl;

    return 0;
}