P6310 "Wdsr-1" Warehouse Construction

One day, a famine broke out in the Human Village.

Because Gensokyo promotes the idea of a “community with a shared future of Gensokyo”, the kappa decided to help humans build some granaries to prevent famine from happening again. The Human Village has $n$ cities and $m$ bidirectional roads. The $i$-th road connects cities $u_i$ and $v_i$, with length $w_i$ units. Since each city has a different technology level, grain-transport trucks starting from different cities have different fuel capacities. The grain-transport trucks in the $i$-th city can only support driving for $x_i$ units. Of course, cities are friendly to each other: no matter which city the truck arrives at, the enthusiastic local people will **refuel it to full**. Kappa technology is highly advanced, so the amount of grain a warehouse can store can be considered infinite. Only warehouses can dispatch grain-transport trucks. Now choose some cities to build warehouses so that every city can receive grain from a warehouse. To save resources, the kappa want the number of warehouses to be as small as possible. However, youkai may sometimes occupy a city, so you need to compute the minimum number of warehouses needed when an arbitrary city is not allowed to build a warehouse.

The first line contains two integers $n, m$, with meanings as described above. The next $m$ lines each contain 3 integers $u_i, v_i, w_i$, with meanings as described above. The next line contains $n$ integers $x_i$, with meanings as described above.

Output one line with $n+1$ integers. The first integer indicates the minimum number of warehouses needed. The next $n$ integers: the $i$-th integer indicates the minimum number of warehouses needed when city $i$ is not allowed to build a warehouse. **If, when city $i$ is not allowed to build a warehouse, building warehouses in other cities still cannot reach this city, output**` -1`.

#### Sample Explanation  This is the graph drawn for the sample. Obviously, building a warehouse in city 3 solves the problem. When city 3 is not allowed to build a warehouse, no matter how you build warehouses in other cities, grain still cannot be transported to city 3, so output ```-1```. --- #### Constraints For $25\%$ of the testdata, $1\le n, m\le 10 ^ 3$ is guaranteed. For another $25\%$ of the testdata, $m=n-1$ is guaranteed. For $100\%$ of the testdata, $1\le n, m \le 3\times 10^5$, $1\le u_i, v_i\le n$, $1\le w_i, x_i\le 10^6$ are guaranteed, and the graph is connected. Translated by ChatGPT 5