The Most Powerful Spell

Long ago there lived a wizard who invented many "magical patterns." In a room where one of his magical patterns is drawn on the floor, anyone can cast magic by uttering a spell. The set of spells available in a room depends on the pattern drawn there. For each given magical pattern, compute the most powerful spell it enables.

A spell is a string of lowercase letters. Among spells, the lexicographically earlier one is more powerful. A string $w$ is lexicographically earlier than a string $u$ when, at the first position where they differ, $w$ has the smaller letter under the order $a < b < \dots < z$, or when $w$ is a prefix of $u$. For example, "abcd" is earlier than "abe" because $c < e$, and "abe" is earlier than "abef" because the former is a prefix of the latter.

A magical pattern is a diagram of uniquely numbered nodes and arrows connecting them. Each arrow has a label, which is a lowercase string. Two nodes are special: the star node and the gold node. A spell becomes usable with a pattern if and only if it equals the concatenation, in order, of the labels along some path from the star node to the gold node.

The figure below shows an example pattern with four nodes and seven arrows.

Here node 0 is the star node and node 2 is the gold node. One usable spell is "abracadabra", produced by the path

0 --abra--> 1 --cada--> 3 --bra--> 2

Another is "oilcadabraketdadabra", produced by the path

0 --oil--> 1 --cada--> 3 --bra--> 2 --ket--> 3 --da--> 3 --da--> 3 --bra--> 2

"abracadabra" is more powerful than "oilcadabraketdadabra" because it is lexicographically earlier. In fact, no other usable spell is more powerful than "abracadabra", so "abracadabra" is the answer for this pattern.

When the most powerful spell cannot be determined, answer "NO". There are two such cases. One is when no path exists from the star node to the gold node. The other is when, for every usable spell, there always exists a more powerful one. The latter is exemplified below: "ab" is more powerful than "b", "aab" is more powerful than "ab", and so on. For any spell, prepending "a" yields a lexicographically earlier (hence more powerful) spell.

The input contains at most 150 datasets. Each dataset has the following format:

n a s g
x_1 y_1 lab_1
x_2 y_2 lab_2
...
x_a y_a lab_a

The first line contains four integers: $n$ is the number of nodes, $a$ is the number of arrows, and $s$ and $g$ are the star node and the gold node, respectively. Each of the next $a$ lines describes one arrow: the line "$x_i\ y_i\ \mathrm{lab}_i$" is an arrow from node $x_i$ to node $y_i$ with label $\mathrm{lab}_i$.

The values satisfy $2 \le n \le 40$, $0 \le a \le 400$, $0 \le s, g, x_i, y_i < n$, $s \ne g$, and each $\mathrm{lab}_i$ is a string of 1 to 6 lowercase letters. Note that self-loops ($x_i = y_i$) may occur, and multiple arrows may connect the same ordered pair of nodes.

The end of the input is indicated by a line containing four zeros: 0 0 0 0.

For each dataset, output a single line containing the most powerful spell for the magical pattern. If no such spell exists, output "NO" (without the quotes). The line must contain no other characters.