imaxblue has successfully killed Fuehrer King Bradley, but he must now escape. His time machine requires a lightning storm to gain enough energy. There are ~N~ cities in Amestris and ~M~ roads. imaxblue is located in city ~A~ and the time machine is in city ~B~. There are ~D~ days before the lightning storm, on which imaxblue must be located in city ~B~. In addition, imaxblue would like to make sure that there are at least ~K~ distinct paths to city ~B~, to make it harder for the Amestris army to track him. Unfortunately, each road has an alertness level. Note that imaxblue must change take a road each day, or the Amestris army will catch up to him.

imaxblue would like to know the minimum alertness level he is required to pass in order to have ~K~ distinct paths of length ~D~ from ~A~ to ~B~, or ~-1~ if it is impossible.

Subtasks

For all cases, ~N \le 100~, ~M \le 10\,000~, ~D, K \le 10^9~.
For ~4~ points, ~D, K=1~.
For additional ~2~ points, ~N, M, D, K \le 10~.
For additional ~4~ points, ~D \le 10~.

Input Specification

Line 1: ~N~, ~M~, ~D~, ~K~, ~A~ and ~B~.
Next ~M~ lines: 3 integers, ~x~, ~y~ and ~w~, representing a bidirectional path from ~x~ to ~y~ with alertness ~w~.
Note: There may be multiple paths between two nodes.

Sample Input

3 5 6 3 0 2
0 1 5
0 0 4
1 2 1
1 2 6
0 2 12

Sample Output

5