Dat je usmereni graf sa ~N~ čvorova i ~M~ grana. Dodatno, svaka grana je obeležena datom vrednošću ~V_{grana}~. Pronaći dužinu najkraćeg puta od čvora ~A~ do čvora ~B~ tako da za svake 2 uzastopne grane ~grana_{i}~, ~grana_{i+1}~ na tom putu važi ~V_{grana_{i+1}} \ge V_{grana_{i}} - K~, gde je ~K~ nenegativan ceo broj dat na ulazu.

Opis ulaza

U prvoj liniji standardnog ulaza nalazi se 5 brojeva: ~N~, ~M~, ~A~, ~B~, ~K~ koji redom označavaju broj čvorova, broj grana, početni čvor, krajnji čvor i ~K~. U narednih ~M~ linija nalaze se po 3 broja: ~X_{i}, Y_{i}, V_{i}~ koji redom predstavljaju čvor od koga kreće jednosmerna grana, čvor u kome se završava i vrednost grane. Čvorovi su numerisani od 0.

Opis izlaza

U prvoj i jedinoj liniji ispisati jedan broj - minimalni broj grana koji treba preći da bi se stiglo od čvora ~A~ do čvora ~B~ sa gore pomenutim uslovom, ili ~-1~ ukoliko takav put ne postoji.

Primeri

3 2 0 2 4
0 1 10
1 2 3

-1

Objašnjenje:

Sa prve grane nije moguće preći na drugu jer je vrednost druge grane manja od 6.

4 4 0 2 4
0 1 10
1 2 3
1 3 6
3 1 4

4

Objašnjenje:

Najkraći put prolazi na početku prvom granom, zatim trećom, četvrtom i na kraju, drugom. Primetimo da opet iz istog razloga kao u prvom primeru ne možemo odmah preći sa prve na drugu granu.

Ograničenja, bodovanje i podzadaci

~2 \le N \le 10^5~, ~0 \le M \le 5*10^5~, ~0 \le A, B < N~, ~A \neq B~, ~0 \le K \le 10^9~
~0 \le X_{i}, Y_{i} < N, X_{i} \neq Y_{i}. 1 \leq V_{i} \leq 10^9~

Test primeri su podeljeni u 4 disjunktne grupe:

• U test primerima vrednim 30 poena: ~N, M, K, V_i \le 100~
  
• U test primerima vrednim 30 poena: ~K, V_i \le 20~
  
• U test primerima vrednim 20 poena: Najviše 20 grana se sastaje na svakom čvoru
  
• U test primerima vrednim 20 poena: Nema dodatnih ograničenja
  

Kod ovog zadatka vam moraju proći svi primeri iz određene grupe kako biste dobili poene za tu grupu.