Background

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

Problem Description

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.

Input Format

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 Format

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.

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

1 1 1 -1 1

Hint

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