# K-Shortest Walk

AC一覧

## Problem Statement問題文

You are given a not necessarily simple graph with $N$ vertices and $M$ edges. The $i$-th edge is directed from vertex $a_i$ to vertex $b_i$ and has weight $c_i$.

For $i$ from $1$ to $K$ (inclusive), output $x_i$, the length of the $i$-th shortest walk from vertex $s$ to vertex $t$. If such walk doesn't exist, output -1.

Multiple walks with the same length are considered different walks.

ただし、長さが同じウォークが複数ある場合別物として考えます。

## Constraints制約

• $1 \leq N, M \leq 300{,}000$
• $1 \leq K \leq 300{,}000$
• $0 \leq s, t < N$
• $0 \leq u_i, v_i < N$
• $0 \leq c_i \leq 10^{7}$

## Input入力

$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}$


## Output出力

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


### # 1

4 5 0 3 5
0 1 1
1 2 1
2 3 1
0 2 1
1 3 1

2
2
3
-1
-1


Timelimit: 5 secs

Before submitting, please confirm terms and conditions