問題文

N 頂点 M 辺の有向グラフがあります。頂点には頂点 1 から頂点 N までの番号が付いており、i 番目の辺 (1\le i\le M) は頂点 u_i から頂点 v_i へ向かう辺で英小文字 c_i が書かれています。また、どの頂点も出次数が 1 以上であることが保証されます。

Alice と Bob がこのグラフを使って以下のようなゲームを行います。

• はじめ、コマが頂点 1 に置かれている。また、空文字列 S を用意する。
• k=1,2,\ldots,2K の順に、k が奇数なら Alice が、偶数なら Bob が以下の操作を行う：
  • 現在コマが置かれている頂点を u_i とする辺 i を 1 本選び、コマを頂点 v_i に動かす。その後、S の先頭に文字 c_i を連結する。

Alice は最終的な S を辞書順でできるだけ小さく、Bob はできるだけ大きくしたいです。

両者が最善を尽くしたときの最終的な S を求めてください。

制約

• 1\le N\le 10^2
• N\le M\le 10^3
• 1\le K\le 10^4
• 1\le u_i,v_i\le N
• c_i は英小文字
• (u_i,v_i,c_i) \neq (u_j,v_j,c_j) (i\neq j)
• x=1,2,\ldots,N に対し u_i=x を満たす i が存在する

入力例 1

3 6 2
1 2 a
2 3 b
3 1 c
2 1 d
3 2 e
1 3 f

出力例 1

deba

両者が最善を尽くしたとき、ゲームは以下のように進行します：

• Alice の手番：辺 1 を選び、コマを頂点 1 から頂点 2 に動かす。S= a となる。
• Bob の手番：辺 2 を選び、コマを頂点 2 から頂点 3 に動かす。S= ba となる。
• Alice の手番：辺 5 を選び、コマを頂点 3 から頂点 2 に動かす。S= eba となる。
• Bob の手番：辺 4 を選び、コマを頂点 2 から頂点 1 に動かす。S= deba となる。

最終的な S は deba となります。

入力例 2

1 1 5
1 1 a

出力例 2

aaaaaaaaaa

入力例 3

4 7 9
1 4 a
3 2 t
4 3 c
2 1 o
4 1 d
3 3 e
2 2 r

出力例 3

rtcadadadadadadada