~N~ cities in Amestris and ~M~ roads. is located in city ~A~ and the time machine is in city ~B~. There are ~D~ days before the lightning storm, on which must be located in city ~B~. In addition, 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 must change take a road each day, or the Amestris army will catch up to him.has successfully killed Fuehrer King Bradley, but he must now escape. His time machine requires a lightning storm to gain enough energy. There are
~K~ distinct paths of length ~D~ from ~A~ to ~B~, or ~-1~ if it is impossible.would like to know the minimum alertness level he is required to pass in order to have
For all cases, ~N\le100~, ~M\le10\,000~, ~D, K\le10^9~.
For ~4~ points, ~D, K=1~.
For additional ~2~ points ~N, M, D, K \le 10~.
For additional ~4~ points ~D \le 10~.
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.
3 5 6 3 0 2 0 1 5 0 0 4 1 2 1 1 2 6 0 2 12