Lazy KUETian
Description
Dreamboy Tashin is a very lazy person. He currently lives in Khan Jahan Ali Hall at KUET for the purpose of studying. He is graduating from Department $\textbf{X}$ at KUET. Since he is very lazy$,$ he always wakes up just a few minutes before his class time and wants to attend his class as early as possible. There are $\textbf{n-1}$ departments in KUET$,$ each in different buildings. There are $m$-directed roads among the $n$ buildings ($n-1$ departments and Khan Jahan Ali Hall)$,$ each road needs some time to traverse$,$ and $\textbf{S}$ is the building number of Khan Jahan Ali Hall. Tashin can also use the reverse roads$,$ but the rules are:
- Tashin can use at most $k$ reverse roads and
- The time required for the reverse roads is twice that of the original roads.
As Tashin is very lazy$,$ you have to help him. You are given $q$ queries$,$ and in each query$,$ you are given the building number of the department that Tashin is graduating from. You have to calculate the minimum time Tashin needs to attend the class.
The first line contains four integers $n,m,k,S$ $(2\le n\le 1000, 1\le m \le min(n\cdot(n-1)/2,1000), 0\le k\le m , 1\le S\le n)$.
The next $m$ lines contain three integers $u,v,t$ $(1 \le u,v \le n,u\neq v, 0 \le t \le 10^{10})$ - indicates that there is a road from $u$ to $v$ which needs $t$ minutes to traverse.
The next line contains an integer $q$ $( 1\le q \le 1000000)$ - the number of queries.
The next q lines contain an integer $X$ $(1 \le X \le n, X\neq S)$ - the building number of the department that Tashin have to reach from his hall $S$.
It is guaranteed that there are no self-loops and multiple roads.
For each query, print the minimum time Tashin needed to reach the building $X$ from the hall $S$. If it is not possible to reach building $X$, then print -1.
Input
The first line contains four integers $n,m,k,S$ $(2\le n\le 1000, 1\le m \le min(n\cdot(n-1)/2,1000), 0\le k\le m , 1\le S\le n)$.
The next $m$ lines contain three integers $u,v,t$ $(1 \le u,v \le n,u\neq v, 0 \le t \le 10^{10})$ - indicates that there is a road from $u$ to $v$ which needs $t$ minutes to traverse.
The next line contains an integer $q$ $( 1\le q \le 1000000)$ - the number of queries.
The next q lines contain an integer $X$ $(1 \le X \le n, X\neq S)$ - the building number of the department that Tashin have to reach from his hall $S$.
It is guaranteed that there are no self-loops and multiple roads.
Output
For each query, print the minimum time Tashin needed to reach the building $X$ from the hall $S$. If it is not possible to reach building $X$, then print -1.
10 10 2 1
1 2 5
10 1 3
4 2 3
2 3 8
3 10 1
3 5 4
4 3 2
6 4 7
7 8 3
8 9 0
5
3
5
6
8
4
8
12
25
-1
11
Note
For the first query$,$ it is optimal to use the reverse roads of $10$ -> $1$ and $3$ -> $10$. So$,$ the path will be $1$ -> $10$ -> $3$$,$ and the time required is $2\cdot3 + 2\cdot1 = 8$ minutes. There is no other path that needs less time than this.