Yuki is a magical girl and she has the ability to activate 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 activate **at most** \(k\) portals.

Now Yuki is curious about what is the **minimum** distance between \(S\) and
\(T\) if she activates at most \(k\) portals.

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 activate 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\)
unidirectionally.

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

Print one line with the result --- the minimum distance between city \(S\) and \(T\).

It is guaranteed that Yuki can move from city \(S\) to \(T\) by activating at most \(k\) portals.