Problem F: Portal (Hard-30) ## Problem F: Portal (Hard-30)

Time Limit: 1 Sec Memory Limit: 128 MB

Submit: 519 Solved: 103

[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

## HINT

[Submit][Status]