Grain Warehouse Optimization in Gensokyo

In Gensokyo, inspired by the idea of a "Gensokyo community of shared destiny," the Kappa decide to help humans build grain warehouses so as to prevent future famines.

There are \(n\) cities and \(m\) bidirectional roads. The \(i\)-th road connects cities \(u_i\) and \(v_i\) with length \(w_i\) units. Due to different technological levels, the grain truck departing from city \(i\) has a fuel capacity of \(x_i\) units, meaning it cannot travel more than \(x_i\) units before requiring a refill. In each city, regardless of origin, vehicles are refueled to full capacity.

Only a city with a warehouse can dispatch grain trucks. The objective is to choose some cities to build warehouses so that every city can receive grain via a path along which each step satisfies: when departing from a city \(i\) to an adjacent city, the road length does not exceed \(x_i\). To conserve resources, the number of warehouses must be minimized.

However, sometimes a monster may occupy a city, rendering it unavailable for a warehouse. For each city, compute the minimum number of warehouses required if that specific city is forbidden from hosting a warehouse. If it becomes impossible to supply grain to all cities under the restriction, output \(-1\) for that case.

Note: All formulas must be written using \( \LaTeX \) format, e.g. \(n\), \(m\), \(x_i\), etc.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n, m \leq 10^5)\) indicating the number of cities and roads.

The second line contains \(n\) integers \(x_1, x_2, \ldots, x_n\) \((1 \leq x_i \leq 10^9)\) where \(x_i\) is the fuel capacity for city \(i\).

Each of the next \(m\) lines contains three integers \(u_i, v_i, w_i\) \((1 \leq u_i, v_i \leq n, 1 \leq w_i \leq 10^9)\) representing a bidirectional road connecting cities \(u_i\) and \(v_i\) with length \(w_i\).

outputFormat

Output a single line with \(n\) integers. The \(i\)-th integer is the minimum number of warehouses needed when city \(i\) is not allowed to have a warehouse. If it is impossible to cover all cities under that restriction, output \(-1\) for that city.

sample

4 4
3 2 3 2
1 2 3
2 3 2
3 4 2
4 1 2

1 1 1 1