#include <bits/stdc++.h>

using namespace std;

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

bool DFS(int node, int dest) {
    if (node == dest) return true;
    if (Vis[node]) return false;

    Vis[node] = true;
    
    for (auto& vec : G[node]) {
        if (DFS(vec, dest)) {
            G[vec].push_back(node);
            swap(vec, G[node].back());
            G[node].pop_back();
            return true;
        }
    }
    return false;
}

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

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

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

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

        while (c--) {
            edges.emplace_back(a, b);
            edges.emplace_back(b, a);
        }
    }

    int offset = 2;
    G[offset].push_back(1);

    int flow = 0;
    while (flow < tot) {
        Vis.assign(G.size(), false);
        if (DFS(0, 1)) {
            flow += 1;
            G[offset].push_back(1);
        } else {
            int noffset = G.size();
            G.resize(noffset + n);
            G[noffset].push_back(1);
            for (auto p : edges) {
                G[offset + p.second].push_back(noffset + p.second);
                G[offset + p.first].push_back(noffset + p.second);
            }
            offset = noffset;
        }
    }
    cout << (offset - 2) / n << endl;

    return 0;
}