34192번 - 최단 경로 쌍

$N$개의 정점과 $M$개의 간선을 가진 방향 그래프가 주어진다. 그래프의 정점은 $1, 2, \dots , N$으로 번호가 매겨져 있다.

정점 $1$을 제외한 모든 정점 $x$에 대하여, 정점 $1$에서 정점 $x$로 가는 최단 경로 쌍을 찾아보고자 한다. 이때, 최단 경로 쌍이란 두 개의 최단 경로 $P, Q$로 구성되어 있으며 다음 두 조건을 만족한다.

• 두 최단 경로에 포함된 정점 집합을 각각 $V_P, V_Q$라 할 때, $(V_P \setminus \{1, x\}) \cap (V_Q \setminus \{1, x\}) = \emptyset$를 만족한다.
• $V_P \neq V_Q$

첫 번째 줄에 정수 $N$과 $M$이 공백으로 구분되어 주어진다. $(2 \le N \le 100\,000;$ $0 \le M \le 300\,000)$

두 번째 줄부터 $M$개의 줄에 걸쳐 세 정수 $u, v, c$가 공백으로 구분되어 주어진다. 이는 정점 $u$에서 정점 $v$로 가는 가중치가 $c$인 간선이 있음을 의미한다. $(1\le u, v \le N;$ $1 \le c \le 10^9;$ $u \neq v)$

임의의 두 정점 $u, v$에 대하여, 정점 $u$에서 정점 $v$로 가는 간선은 최대 하나만 주어진다.

첫 번째 줄에 $N - 1$개의 정수를 공백으로 구분하여 출력하라. 이 중 $i$번째 정수는, 정점 $1$에서 정점 $i+1$로 가는 최단 경로 쌍이 존재하면 $1$, 아니면 $0$이다.

정점 $a$에서 정점 $b$로의 최단 경로란 정점 $a$에서 정점 $b$로 가는 경로 중 가중치의 합이 가장 작은 경로를 의미한다.