다익스트라

$1$부터 $N$까지 번호가 붙은 $N$개의 정점과 $M$개의 간선으로 이루어진 무방향 그래프가 있다.

각 간선에는 양의 가중치가 있다.

시작 정점 $S$로부터 각 정점까지의 최단 거리를 구하라.

첫 번째 줄에 정점의 개수 $N$, 간선의 개수 $M$, 시작 정점 $S$가 주어진다. $(1 \leq N \leq 100\,000, 0 \leq M \leq 200\,000, 1 \leq S \leq N)$

두 번째 줄부터 $M$개의 줄에 걸쳐 간선으로 연결된 두 정점 $u$, $v$와 간선의 가중치 $w$가 주어진다. $(1 \leq u,v \leq N, u \neq v, 1 \leq w \leq 10^9)$

단, 같은 두 정점을 연결하는 간선은 두 번 이상 주어지지 않는다.

$1$번 정점부터 $N$번 정점까지 시작 정점 $S$로부터의 최단 거리를 한 줄에 하나씩 출력한다.

시작 정점에서 도달할 수 없는 정점이라면 -1을 출력한다.