Problem E: Doragoso Ball

Problem

L 個集めるとドラゴソが現れどんな願いでも一つだけ叶えてくれるというドラゴソボールがとある迷宮に散らばっている。入口からスタートし、途中で立ち止まることなくすべてのボールを回収し、それらを迷宮内にある祭壇に奉納し、そのまま呪文を唱えるとドラゴソが現れ願いを叶えてくれるという。ただし、呪文を唱え始める時間は入口からボールを奉納するまでのルートのうち、移動時間が K 番目に短いルートで移動したときの時間でなければならない。

この迷宮は部屋とわたり通路からなり、部屋と部屋はわたり通路を通る事によって行き来できる。ドラゴソボールはそれらの数ある部屋のどこかに落ちている。なお、迷宮は入り口から祭壇へたどりつく道が存在しない可能性もあるようだ。また、移動時間はわたり通路の移動だけを考慮し、部屋の中を移動する時間、ボールを拾うときにかかる時間、祭壇に奉納する時間は考慮しなくてよい。また、同じ通路や同じ部屋に何度も訪れてもよいが、ドラゴソボールがある部屋に初めて入った場合は、そのボールを拾うことにする。祭壇に到達したとき、必ずしもボールを納めなければならないわけではない。

迷宮の内部構造の情報と迷宮の入り口、祭壇の場所とボールの数 L とボールの配置場所と求められている最短な経路の順位 K が与えられるので、呪文を唱え始めるべき時間を求めよ。

また、異なる移動ルートでも、移動時間が同じである場合はそれらのルートは同じ順位として扱う。
例えば、

ルートA 時間 2
ルートB 時間 5
ルートC 時間 5
ルートD 時間 5
ルートE 時間 5
ルートF 時間 7

このようなとき、ルートB,C,D,Eは2位かつ3位かつ4位かつ5位として扱う。ルートFは6位として扱う。

Input

入力は複数のデータセットからなる。
各データセットは以下のフォーマットで表される。

N M L K
u1 v1 c1
…
uM vM cM
S G
B1
B2
…
BL

最初に N , M , L , K が与えられる。
それぞれ、部屋の数、わたり通路の数、ボールの数、求められている最短な経路の順位を表す。それぞれの部屋は1〜 N で番号付けされる。
次に M 行にわたり通路の情報、 u_i , v_i , c_i が与えられる。
部屋 u_i , v_i 間にわたり通路が存在し、通過するのに時間 c_i がかかることを表す。
次に S , G が与えられる。
それぞれ、迷宮の入り口と祭壇がある部屋番号を表す。
次に L 行にわたってドラゴソボールが落ちている部屋の番号 B_i ( 1 ≤ i ≤ L )が与えられる。

入力の終わりは4つのゼロからなる。

Constraints

入力は以下の条件を満たす。

• 入力に含まれる値はすべて整数
• 2 ≤ N ≤ 50
• 0 ≤ M ≤ 1225
• 1 ≤ L ≤ 7
• 1 ≤ K ≤ 10
• 1 ≤ S , G ≤ N
• 1 ≤ B_i ≤ N ( 1 ≤ i ≤ L )
• B_i ≠ B_j ( 1 ≤ i < j ≤ L )
• 1 ≤ u_i , v_i ≤ N ( 1 ≤ i ≤ M )
• 1 ≤ c_i ≤ 1000 ( 1 ≤ i ≤ M )
• データセットは最大10個である

Output

各データセットに対し、呪文を唱え始めるべき時間を1行に出力せよ。 K 番目に短い経路が存在しない場合は"NA"を1行に出力せよ。

Sample Input

9 14 5 10
1 2 1
1 4 5
2 4 4
2 3 3
2 6 2
3 6 3
3 7 2
4 6 5
4 5 6
5 8 8
6 7 3
7 8 1
7 9 9
8 9 2
1 9
1
2
5
7
9
4 5 1 3
1 2 1
1 3 2
2 3 2
2 4 9
3 4 1
1 4
2
4 5 1 10
1 2 1
1 3 2
2 3 2
2 4 9
3 4 1
1 4
2
4 3 1 1
1 2 1
2 3 1
3 4 1
1 4
1
4 3 1 2
1 2 1
2 3 1
3 4 1
1 4
1
4 3 1 10
1 2 1
2 3 1
3 4 1
1 4
1
2 1 1 1
1 2 1
1 2
1
2 1 1 10
1 2 1
1 2
1
4 2 1 4
1 2 1
3 4 1
1 4
2
0 0 0 0

Sample Output

27
6
8
3
5
7
1
19
NA

---