410478: GYM104025 D ZYW with BIT

Although ZYW has graduated from BIT, he still comes to BIT often to have dinner with his friends. After a period of observation, ZYW found that the traffic light cycle of all intersections near BIT is $$$T$$$, which means that for any traffic light, the color of it is same at time $$$t_0$$$ and time $$$t_0+T$$$ for any $$$t_0$$$.

After detailed investigation, ZYW records the schedule of traffic light changes, i.e., the time when passing is allowed and the time when passing is not allowed. Note that the traffic light in this city allows people to enter the intersection at any time, but all people must leave the intersection within the allowed time period.

In this city there are $$$n$$$ intersections and $$$m$$$ bidirectional roads. The $$$i$$$-th road connects the $$$u_i$$$-th intersection with the $$$v_i$$$-th intersection and takes $$$w_i$$$ time to pass. BIT is at the $$$n$$$-th intersection and ZYW's home is at the $$$1$$$-st intersection. Now ZYW wants to know the minimum time it takes to get from his house to BIT at any time from $$$0$$$ to $$$T-1$$$.

The first line contains three integers $$$n,m,T\ (1\le n,T\le 500, 1\le m\le 2000) $$$, indicating there are $$$n$$$ intersections and $$$m$$$ roads in this city and the cycle of each traffic light is $$$T$$$.

In the next $$$n$$$ lines, each line contains a $$$\text{01}$$$ string of length $$$T$$$. The $$$i$$$-th intersection is allowed to pass at time $$$j$$$ if the $$$j$$$-th character in the $$$i$$$-th line is $$$\text{1}$$$, and not allowed to pass otherwise.

In the next $$$m$$$ lines, each line contains three integers $$$u,v,w\ (1\le u,v\le n,1\le w\le 10^9) $$$, indicating a road connecting $$$u$$$ and $$$v$$$ intersections, and it takes $$$w$$$ time to pass.

Output $$$T$$$ integers representing the minimum time ZYW needs to reach BIT if ZYW starts from each time in $$$[0, T)$$$.

It is guaranteed that ZYW can reach BIT.

4 4 5
11111
00001
01000
00000
1 2 1
2 4 1
1 3 1
3 4 1

2 4 3 2 3