Professor Ford needs to get to an international conference. He wants to spend the least amount of money on the road, so he decided that he would travel exclusively by night flights (so as not to spend money on overnight stays in hotels), and during the day he would see the sights of the cities through which he would transit. He carefully studied the flight schedule and compiled a set of suitable flights, figuring out that flights to the selected destinations were made every night and he could not make two flights in one night.
Now the professor wants to find the path of least cost, given that there are K nights left before the conference (that is, the professor can make no more than K flights).
Input
The first line contains the numbers N (number of cities), M (number of flights), K (number of remaining nights), S (number of the city where the professor lives), F (number of the city where the conference is held).
Limits: 2≤N≤100, 1≤M≤105, 1≤K≤100, 1≤S≤N, 1≤F≤N.
Then there are M lines specifying the flight schedule. The i-th line contains three natural numbers: Si, Fi and Pi, where Si - number of the city from which the i-th flight departs, Fi - number of the city to which the i-th flight arrives, Pi - cost of the i-th flight . 1≤Si≤N, 1≤Fi≤N, 1≤Pi≤106.
Output
Print a single number - the minimum cost of a path suitable for the professor. If the professor cannot get to the conference in K nights, print the number -1.