0148 - 最強の呪文

昔々，多くの「魔法の紋様」を発明した魔法使いがいた．
彼の発明した魔法の紋様が床に描かれた部屋では，
呪文を唱えることで，誰でも魔法が使えるようになるのだ！
ただし，使える呪文は紋様によってまちまちである．
あなたの仕事は，指定された魔法の紋様に対し，
それによって使用可能となる呪文のうち，最強のものを突き止めることだ．

呪文は，英小文字の文字列であり，
特に辞書順で早ければ早い呪文であるほど，強い呪文である．
ここで文字列 w が文字列 u より辞書順で早いとは，
w と u とで異なる最初の文字が a<b<...<z の順序で小さいか，
または w が u の接頭辞であることを言う．
例として，"abcd" は "abe" より早く（文字 c は e より小さいため），
また，"abe" は "abef" より早い（接頭辞になっているため）．

魔法の紋様は，番号のついた 節点 と，それらを結ぶ矢印
からなる図形である．
矢印には ラベル と呼ばれる小文字の文字列がついている．
また，スター とゴールド と呼ばれる，
二つの特別な節点がある．
魔法の紋様によって使えるようになる呪文とはすなわち，
その紋様のスターからゴールドへと矢印をたどって得られるラベルを順に結合して得られる文字列である．

次に，四つの節点と7本の矢印からなる例を図示する．

0 がスター，2 がゴールドである．
この魔法の紋様によって，例えば

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

という経路から得られる呪文 "abracadabra" が使えるようになる．他には，

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

から得られる "oilcadabraketdadabra" などもある．
"abracadabra" と "oilcadabraketdadabra" では前者の方が辞書順で早いので，より強い呪文である．
実は，この魔法の紋様で使用可能となる呪文で "abracadabra" 以上に強いものは存在しない．
従ってこの場合，あなたが求めるべき答えは "abracadabra" となる．

もしも，最強の呪文が定められないときには，"NO" と答えて欲しい．
これには二つの場合がある．一つは，スターからゴールドへ到達できない場合である．
もう一つは，どんな呪文をとっても，
それよりさらに強い呪文が存在するような場合である．
たとえば次の図のような魔法の紋様では，
"b" よりも "ab" が強く，
"ab" よりも "aab" が強いといったように，
どの呪文をとってもさらに一つ a を増やすと，辞書順で早い，より強い呪文となる．

入力は最大で150個のデータセットからなる．
各データセットの形式は次のとおりである．

n a s g

x₁ y₁ lab₁

x₂ y₂ lab₂

...

x_a y_a lab_a

データセットの最初の行は4個の整数を含む．n は節点の数，a は矢印の数を表す．
s と g はそれぞれスターとゴールドの番号を示す．
続く a 行はそれぞれ2個の整数と1個の文字列からなり，矢印の情報を表す．
x_i y_i lab_i という行は，
節点 x_i から出て節点 y_i を指す，
ラベルが lab_i の矢印を表している．
データセット中の値は次の条件を満たす：
2 ≤ n ≤ 40,
0 ≤ a ≤ 400,
0 ≤ s, g, x_i , y_i < n.
s ≠g,
lab_i は長さ1以上6以下の，英小文字のみからなる文字列である．
矢印の両端が同一節点の場合 (x_i = y_i ) や，
節点の対を複数の矢印が結ぶ場合
(異なる i, j に対し
x_i = x_j かつ y_i = y_j )
もあり得ることに注意して欲しい．

入力の終わりは4個のゼロからなる行によって与えられる．

各データセットについて，最も強い呪文が存在すれば，それぞれ1行に出力しなさい．
存在しない場合は NO を1行に出力しなさい．
各出力行はこれ以外の文字を含んではならない．

4 7 0 2
0 1 abra
0 1 oil
2 0 ket
1 3 cada
3 3 da
3 2 bra
2 3 ket
2 2 0 1
0 0 a
0 1 b
5 6 3 0
3 1 op
3 2 op
3 4 opq
1 0 st
2 0 qr
4 0 r
2 1 0 1
1 1 loooop
0 0 0 0

abracadabra
NO
opqr
NO