Bitocja

Bitocja라는 나라에 BitBank의 부유한 사장 Bitazar가 살고 있다. 그는 매일 도시 $1$에서 도시 $n$까지 이동하여 출근한다. Bitocja에는 이미 양방향 도로망이 있어 Bitazar가 목적지에 도달할 수 있지만, 그는 이동 시간이 너무 길다고 느낀다. 그래서 그는 출퇴근 시간을 줄여 줄 새 도로 건설 제안을 건설 회사들로부터 받았고, 받은 제안들을 주어진 순서대로 하나씩 검토한다. 각 제안에 대해, 그 도로를 건설하면 도시 $1$에서 도시 $n$까지의 현재 최단 이동 시간이 엄밀히 줄어드는지를 확인한다.

• 줄어든다면 그 도로를 건설하며, 건설된 도로는 도로망에 계속 남는다. 이후 제안들은 갱신된 도로망을 기준으로 검토한다.
• 줄어들지 않는다면 그 제안은 거절되고 도로망은 그대로 유지된다.

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 기존 도로들과 새로 제안된 연결들을 읽는다.
• 각 제안된 도로에 대해 Bitazar의 조건을 만족하는지 판정한다.
• 결과를 표준 출력에 쓴다.

첫 번째 줄에 세 정수 $n$, $k$, $m$이 주어진다 ($1 \le n \le 100$, $1 \le k \le \frac{n(n-1)}{2}$, $1 \le m \le 10000$). 각각 도시의 수(도시는 $1$부터 $n$까지 번호가 매겨진다), 이미 건설된 도로의 수, 새로 제안된 도로의 수이다.

이어지는 $k$개의 줄에는 기존 도로가 하나씩 주어진다. 그다음 $m$개의 줄에는 제안된 도로가 검토되는 순서대로 하나씩 주어진다. 각 도로는 세 정수 $a$, $b$, $w$로 주어지며 ($1 \le a, b \le n$, $1 \le w \le 1000000$), 도시 $a$와 $b$를 잇는 양방향 도로이고 그 도로의 이동 시간이 $w$임을 뜻한다.

$m$개의 줄을 출력한다. $i$번째 제안된 도로에 대해, Bitazar가 그 제안을 받아들여야 하면(그 도로가 도시 $1$에서 도시 $n$까지의 최단 이동 시간을 엄밀히 줄이면) $1$을, 거절해야 하면 $0$을 출력한다.