Problem F: Portal (Hard-30)

Problem F: Portal (Hard-30)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 523  Solved: 106
[Submit][Status][Web Board]

Description

Yuki is a magical girl and she has the ability to active portals.

The country Yuki lives in has $$n$$ cities and $$m$$ roads at certain distances. The cities are numbered from $$1$$ to $$n$$ and all the roads are unidirectional, that is a road from $$u$$ to $$v$$ cannot be passed from $$v$$ to $$u$$. Also, there are $$p$$ portals in the country, each of them connects two cities unidirectional with no distance. Since Yuki doesn’t grasp magic thoroughly, she can active at most $$k$$ portals.

Now Yuki is curious about what is the minimum distance between $$S$$ and $$T$$ if she actives at most $$k$$ portals.

Input

The first line contains four integers: $$n$$, $$m$$, $$p$$ and $$k$$ $$(1\leq n,m,p\leq 50\ 000,0\leq k\leq10)$$ — the number of cities, roads, portals and the number of portals Yuki can active at most.

Each of the next $$m$$ lines contains three integers: $$u$$, $$v$$ and $$w$$ $$(1 \leq u,\ v\leq n,1\leq w\leq 1\ 000\ 000)$$, meaning that there is a unidirectional road from city $$u$$ to city $$v$$ at distance $$w$$.

Each of the next $$p$$ lines contains two integer: $$u$$ and $$v$$ $$(1 \leq u,\ v\leq n)$$, meaning that there is an inactive portal from city $$u$$ to city $$v$$. Please note that when it is active, Yuki can only be teleported from city $$u$$ to $$v$$ unidirectional.

The last line contains two integers: $$S$$ and $$T$$ $$(1\leq S,T\leq n)$$ — the origin and destination.

Output

Print one line with the result — the minimum distance between $$S$$ and $$T$$.

Sample Input

5 6 3 1
1 3 4
1 2 2
3 5 6
2 4 3
3 4 1
4 5 2
2 3
1 4
1 2
1 5


Sample Output

2


[Submit][Status]