/*
author: Maksim1744
created: 04.12.2021 11:30:50
*/
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
template<typename T> vector<T>& operator-- (vector<T> &v){for (auto& i : v) --i; return v;}
template<typename T> vector<T>& operator++ (vector<T> &v){for (auto& i : v) ++i; return v;}
template<typename T> istream& operator>>(istream& is, vector<T> &v){for (auto& i : v) is >> i; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T> v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator-- (pair<T, U> &p){--p.first; --p.second; return p;}
template<typename T, typename U> pair<T,U>& operator++ (pair<T, U> &p){++p.first; ++p.second; return p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second; return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U> p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}
#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun) fun
#define debugv(var) var
#define mclock void(0)
#define shows void(0)
#define debug if (false)
#endif
template<class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
// auto gcd = std::y_combinator([](auto gcd, int a, int b) -> int {
// return b == 0 ? a : gcd(b, a % b);
// });
vector<int> scc(vector<vector<int>>& g, vector<vector<int>>& gi) {
int n = g.size();
vector<int> topsort; topsort.reserve(n);
vector<bool> u(n, false);
auto scc_dfs1 = y_combinator([&](auto scc_dfs1, int v) -> void {
u[v] = true;
for (auto k : g[v])
if (!u[k])
scc_dfs1(k);
topsort.push_back(v);
});
for (int i = 0; i < n; ++i)
if (!u[i])
scc_dfs1(i);
int color = 0;
vector<int> comp(n, -1);
reverse(topsort.begin(), topsort.end());
auto scc_dfs2 = y_combinator([&](auto scc_dfs2, int v, int color) -> void {
comp[v] = color;
for (auto k : gi[v])
if (comp[k] == -1)
scc_dfs2(k, color);
});
for (auto v : topsort)
if (comp[v] == -1)
scc_dfs2(v, color++);
return comp;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size();
vector<vector<pair<int, pair<int, int>>>> g(n);
for (int i = 0; i < u.size(); ++i) {
g[u[i]].eb(v[i], mp(i * 2 + 0, c[i]));
g[v[i]].eb(u[i], mp(i * 2 + 1, c[i]));
}
vector<vector<int>> go(n);
vector<vector<int>> goi(n);
vector<bool> ue(u.size() * 2, false);
bool because_change = false;
vector<int> cur(n, 0);
int icur = 0;
for (int iter = 0; iter < 1e2/2; ++iter) {
bool change = false;
auto col = scc(go, goi);
vector<vector<int>> comps(maxe(col) + 1);
for (int i = 0; i < n; ++i) {
comps[col[i]].pb(i);
}
for (int i = 0; i < comps.size(); ++i) {
++icur;
for (int v : comps[i]) {
cur[r[v]] = icur;
}
for (int v : comps[i]) {
for (auto [u, ic] : g[v]) {
auto [ind, c] = ic;
if (col[u] == col[v]) continue;
if (cur[c] != icur) continue;
if (ue[ind]) continue;
ue[ind] = true;
go[v].pb(u);
goi[u].pb(v);
change = true;
}
}
}
show(go, change);
if (!change) {
because_change = true;
break;
}
}
auto col = scc(go, goi);
vector<bool> terminal(maxe(col) + 1, true);
for (int i = 0; i < n; ++i) {
for (auto j : go[i]) {
if (col[i] == col[j]) continue;
terminal[col[i]] = false;
}
}
show(go);
show(col);
show(terminal);
vector<int> sz(terminal.size(), 1e9);
vector<pair<int, vector<int>>> tos(n, {-1, {}});
vector<int> has(n, -1);
int ihas = 0;
vector<bool> uu(n, false);
auto reachable = [&](int v) {
++ihas;
queue<int> q;
int ans = 0;
q.push(v);
uu.assign(n, false);
while (!q.empty()) {
auto v = q.front();
q.pop();
if (uu[v]) continue;
uu[v] = true;
++ans;
if (has[r[v]] != ihas) {
has[r[v]] = ihas;
if (tos[r[v]].first != ihas) tos[r[v]].second.clear();
for (int k : tos[r[v]].second)
q.push(k);
}
for (auto [k, ic] : g[v]) {
auto [ind, c] = ic;
if (has[c] == ihas)
q.push(k);
else {
if (tos[c].first != ihas) {
tos[c].first = ihas;
tos[c].second.clear();
}
tos[c].second.pb(k);
}
}
}
show(v, ans);
return ans;
};
if (because_change) {
for (int i = 0; i < n; ++i) {
if (terminal[col[i]])
sz[col[i]] = 0;
}
for (int i = 0; i < n; ++i) {
sz[col[i]]++;
}
} else {
vector<int> check;
for (int i = 0; i < n; ++i) {
if (terminal[col[i]]) {
terminal[col[i]] = false;
check.pb(i);
}
}
for (int v : check) {
sz[col[v]] = reachable(v);
}
}
show(sz);
vector<int> ans(n, 0);
int mnsz = mine(sz);
for (int i = 0; i < n; ++i) {
if (sz[col[i]] == mnsz) {
ans[i] = 1;
}
}
return ans;
}
#ifdef HOUSE
int main() {
int n, m;
assert(2 == scanf("%d%d", &n, &m));
std::vector<int> r(n), u(m), v(m), c(m);
for(int i=0; i<n; i++) {
assert(1 == scanf("%d", &r[i]));
}
for(int i=0; i<m; i++) {
assert(3 == scanf("%d %d %d", &u[i], &v[i], &c[i]));
}
fclose(stdin);
std::vector<int> ans = find_reachable(r, u, v, c);
for (int i = 0; i < (int) ans.size(); ++i) {
if(i) putchar(' ');
putchar(ans[i]+'0');
}
printf("\n");
return 0;
}
#endif
