#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <queue>
 
using namespace std;
 
const int dim = 105;
 
ifstream in("algola.in");
ofstream out("algola.out");
 
vector <int> vec[3*dim];
 
int t[3*dim],viz[3*dim],c[3*dim][3*dim],n,m,val[dim],d[3*dim][3 *dim],suma;
 
int BFS(int sursa,int destinatie)
{
    memset(viz,0,sizeof(viz));
    queue<int> q;
    q.push(sursa);
    viz[sursa] = 1;
    while (!q.empty())
    {
        int x = q.front();
        ///  cout << x << " ";
        q.pop();
        if (x == destinatie) continue;
        for (int j=0; j<vec[x].size(); j++)
        {
            int y = vec[x][j];
            if (!viz[y] && c[x][y] > 0)
            {
                viz[y] = 1;
                t[y] = x;
                q.push(y);
            }
        }
    }
    ///cout << endl;
    return viz[destinatie];
}
 
int Get_Flux(int sursa,int destinatie)
{
    int maxflow = 0;
    int fmin = 1e9;
    ///cout << BFS(sursa, destinatie, vec,c) << "\n";
    /// int ok =
    int ok = BFS(sursa, destinatie);
    while (ok)
    {
        for (int j=0; j<vec[destinatie].size(); j++)
        {
            int y = vec[destinatie][j];
            //cout << y << " ";
 
            t[destinatie] = y;
            fmin = 1e9;
            for (int i=destinatie; i != sursa ; i=t[i])
            {
                fmin = min(fmin, c[t[i]][i]);
            }
            for (int i=destinatie; i != sursa ; i=t[i])
            {
                c[t[i]][i] -= fmin;
                c[i][t[i]] += fmin;
            }
            /// cout << maxflow < " ";
            maxflow += fmin;
        }
        ok = BFS(sursa, destinatie);
        ///ok = 0;
    }
    return maxflow;
}
 
int main()
{
    in >> n >> m;
    for (int i=1; i<=n; i++)
    {
        in >> val[i];
        suma += val[i];
    }
    int sursa = 0;
    for (int i=1; i<=n; i++)
    {
        vec[i].push_back(sursa);
        vec[sursa].push_back(i);
        c[sursa][i] = val[i];
    }
    for (int i=1; i<=m; i++)
    {
        int x,y,f;
        in >> x >> y >> f;
        vec[x].push_back(y);
        vec[y].push_back(x);
        d[x][y] = f;
		d[y][x] = f;
    
    for (int i=1; i<=m; i++)
    {
        for (int j=1; j<=n; j++)
        {
            for (int z=0; z<vec[j].size(); z++)
            {
                c[i][vec[j][z]] = d[i][vec[j][z]] * i;
            }
        }
        for (int i=1; i<=n; i++)
        {
            if (val[i] == 0) val[i] = 1e9;
            c[sursa][i] = val[i];
        }
        int dapa = Get_Flux(sursa, 1);
        if (dapa >= suma)
        {
            out << i;
            return 0;
        }
    }
    return 0;
}