#214571. [2019 KAIST RUN Fall] Lexicographically Minimum Walk

There is a directed graph with nodes and edges. Each node is numbered through , and each edge is numbered through . For each (), edge goes from vertex to vertex and has a color .

A is defined as a sequence of edges , , , where for each , (the tail of edge ) is the same as (the head of edge ). We can say a walk starts at vertex and ends at vertex . Note that the same edge can appear multiple times in a walk.

The of a walk is defined as .

Consider all color sequences of walks of length at most from vertex to vertex in . Write a program that finds the lexicographically minimum sequence among them.

The first line of the input contains four space-separated integers , , , and (, , , , ).

Then lines follow: the ()-th of them contains three space-separated integers , and (, , ); it describes a directional edge from vertex to vertex with color .

The graph doesn't have multiple edges and each edge has a unique color. Formally, for any , and holds.

If there is no walk from vertex to vertex , print . (without quotes)

Otherwise, let's say is the lexicographically minimum sequence among all color sequences of length at most from vertex to vertex .

• If , print in the first line. There should be a space between each printed integer.
• If , print . (without quotes)

样例输入 1

3 3 1 3
1 2 1
2 3 7
1 3 5

样例输出 1

1 7

样例输入 2

3 4 1 3
1 2 1
2 1 2
2 3 7
1 3 5

样例输出 2

TOO LONG

样例输入 3

2 0 2 1

样例输出 3

IMPOSSIBLE

Sequence is lexicographically smaller than another sequence if and only if one of the following holds:

• There exists a unique () where , , , and .
• and , , , . In other words, is a strict prefix of .