#include <fstream>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

ifstream in ("algola.in");
ofstream out ("algola.out");

const int max_size = 5e3 + 9, INF = 1e9 + 1;

int cap[max_size][max_size], capog[max_size][max_size], uz[max_size], t[max_size], viz[max_size], ans, fluxcurr, s, n;
vector <int> mc[max_size], grafog[max_size];

bool bfs ()
{
    queue <int> q;
    for (int i = 0; i <= 5008; i++)
    {
        uz[i] = 0;
        t[i] = 0;
    }
    q.push(0);
    while (!q.empty())
    {
        int nod = q.front();
        q.pop();
        for (auto f : mc[nod])
        {
            if (!uz[f] && cap[nod][f] > 0)
            {
                t[f] = nod;
                if (f == 5008)
                {
                    return true;
                }
                uz[f] = 1;
                q.push(f);
            }
        }
    }
    return false;
}

void flux ()
{
    while (bfs())
    {
        int mn = INF, nod = 5008;
        while (nod != 0)
        {
            mn = min(mn, cap[t[nod]][nod]);
            nod = t[nod];
        }
        if (mn <= 0)
        {
            continue;
        }
        fluxcurr += mn;
        nod = 5008;
        while (nod != 0)
        {
            cap[t[nod]][nod] -= mn;
            cap[nod][t[nod]] += mn;
            nod = t[nod];
        }
    }
}

int main ()
{
    int m;
    in >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        in >> cap[0][i];
        mc[0].push_back(i);
        mc[i].push_back(0);
        s += cap[0][i];
    }
    while (m--)
    {
        int x, y, c;
        in >> x >> y >> c;
        grafog[x].push_back(y);
        grafog[y].push_back(x);
        capog[x][y] = c;
        capog[y][x] = c;
    }
    mc[1].push_back(5008);
    cap[1][5008] = INF;
    flux();
    while (fluxcurr < s)
    {
        ans++;
        cout << ans << " ";
        mc[ans * n + 1].push_back(5008);
        cap[ans * n + 1][5008] = INF;
        for (int i = 1; i <= n; i++)
        {
            for (auto f : grafog[i])
            {
                mc[(ans - 1) * n + i].push_back(ans * n + f);
                mc[ans * n + f].push_back((ans - 1) * n + i);
                cap[(ans - 1) * n + i][ans * n + f] = capog[i][f];
            }
            mc[(ans - 1) * n + i].push_back(ans * n + i);
            mc[ans * n + i].push_back((ans - 1) * n + i);
            cap[(ans - 1) * n + i][ans * n + i] = INF;
        }
        flux();
    }
    out << ans;
    in.close();
    out.close();
    return 0;
}