22933번 - TraveLog 다국어

문제

After a long time apart, Alice and Bob have reunited. They live in a country with $n$ cities, creatively named city 1ドル$ to city $n$. Bob drove from his home in city 1ドル$ to Alice's home in city $n$.

When Alice asked Bob which path he took, he was stunned to find he didn't remember. Bob is efficient, and drove without stopping, and knows there is no path faster than the one he took. He also has a brand new National Adventuring Company (NAC) TraveLog! Every time Bob drives through a city, the TraveLog records the time between when he left city 1ドル$ and when he arrived in the current city.

In the above layout, there are two possible fastest paths Bob can take from city 1ドル$ to city $n$: 1ドル \to 2 \to 3 \to 5$ or 1ドル \to 4 \to 5$. Both paths take a total of 9ドル$ units of time. The first path would have a TraveLog of 0,ドル 3, 7, 9,ドル and the second would have a TraveLog of 0,ドル 5, 9$.

Unfortunately, the memory in Bob's TraveLog is corrupted. Bob thinks that some of the times are gone, and the remaining times are shuffled arbitrarily. Given what remains of the TraveLog, can you reconstruct Bob's path?

입력

The first line of input contains three integers $n$ (2ドル \le n \le 2 \cdot 10^{5}$), $m$ (1ドル \le m \le 3 \cdot 10^{5}$) and \mbox{$d$ (1ドル \le d \le n$)}, where $n$ is the number of cities in the country, $m$ is the number of one-way roads between those cities, and $d$ is the number of times remaining in Bob's corrupted TraveLog. The cities are identified by number, 1ドル$ through $n$. Bob lives in city 1ドル,ドル and Alice lives in city $n$.

Each of the next $m$ lines contains three integers $u,ドル $v$ (1ドル \le u,v \le n, u \ne v$) and $h$ (1ドル \le h \le 10^{6}$). Each line describes a one-way road from city $u$ to city $v$ that takes $h$ units of time to traverse. There is guaranteed to be at least one path from city 1ドル$ to city $n$. There may be several roads between any given pair of cities.

Each of the next $d$ lines contains a single integer $t$ (0ドル \le t \le 10^{18}$). This is what remains of Bob's TraveLog. Each line is a record of the amount of time Bob took driving from city 1ドル$ to another city on his path. These values are guaranteed to be distinct.

출력

The output format depends on the number of paths consistent with Bob's TraveLog.

• If there is no path consistent with Bob's TraveLog, output 0ドル$.
• If multiple paths are consistent with Bob's TraveLog, output 1ドル$.
• Otherwise, on the first line, output the number of cities on Bob's path. On subsequent lines, output the cities Bob visited, one per line, in the order he visited them.

제한

힌트