K-최단 보행

$N$개의 정점과 $M$개의 간선을 가지며 단순 그래프일 필요는 없는 유향 그래프가 주어진다. $i$번째 간선은 정점 $a_i$에서 정점 $b_i$로 향하며 가중치는 $c_i$이다.

$1$ 이상 $K$ 이하의 각 $i$에 대해, 정점 $s$에서 정점 $t$로 가는 $i$번째 최단 보행의 길이 $x_i$을 출력한다. 그러한 보행이 존재하지 않으면 -1을 출력한다.

길이가 같은 여러 보행은 서로 다른 보행으로 간주한다.

제약 조건

• $1 \leq N, M \leq 300000$
• $1 \leq K \leq 300000$
• $0 \leq s, t < N$
• $0 \leq u_i, v_i < N$
• $0 \leq c_i \leq 10000000$

$N~M~s~t~K$
$u_0~v_0~c_0$
$u_1~v_1~c_1$
$u_2~v_2~c_2$
:
$u_{M-1}~v_{M-1}~c_{M-1}$

$x_1$
$x_2$
$\vdots$
$x_K$