팬 그룹

한 도시에 $1$번부터 $n$번까지 번호가 매겨진 광장 $n$개가 있고, 이들을 잇는 일방통행 도로 $m$개가 있습니다. 이 도시에는 축구 팬 그룹도 $n$개 있으며, 팬 그룹 $i$의 본부는 광장 $i$에 있습니다.

어느 날 팬 그룹들은 "도시 투어"를 벌입니다. 미리 정해 둔 순서에 따라 그룹들이 한 번에 하나씩 광장을 점령해 나갑니다. 처음에는 어떤 광장도 점령되어 있지 않습니다. 그룹들은 엄격히 차례대로 움직이며, 한 그룹은 바로 앞 그룹이 자기 차례를 끝낸 뒤에야 시작합니다.

팬 그룹 $i$의 차례가 되면:

• 광장 $i$가 이미 다른 그룹 $j \ne i$에게 점령되어 있다면, 그룹 $i$는 아무것도 하지 않습니다.
• 그렇지 않다면, 그룹 $i$는 광장 $i$를 점령한 뒤 퍼져 나갑니다. 어떤 광장 $v$를 점령할 때마다 그룹은 $v$에서 나가는 모든 도로로 팬들을 보냅니다. 도로 $v \to w$에 대해: $w$가 이미 다른 그룹에게 점령되어 있으면 지나갈 수 없어 그 도로에서 싸움이 벌어집니다. $w$가 아직 점령되지 않았으면 그룹은 $w$도 점령하고 거기서부터 계속 퍼져 나갑니다.
• 더 이상 도달할 수 있는 빈 광장이 없으면 차례가 끝납니다.

두 그룹은 싸움이 벌어진 도로에서 정확히 마주치므로, 싸움 기록은 어느 도로가 막혔는지를 그대로 알려 줍니다. 도시 지도와 함께 각 도로에서 싸움이 일어났는지 여부가 주어질 때, 그룹들이 움직였을 수 있는 순서를 복원하세요.

첫째 줄에 광장의 수 $n$과 일방통행 도로의 수 $m$이 주어집니다. 다음 $m$개의 줄에는 각각 세 정수 $a$, $b$, $c$가 주어지며, 이는 광장 $a$에서 광장 $b$로 가는 일방통행 도로를 나타냅니다. $c = 1$이면 이 도로에서 싸움이 일어났고, $c = 0$이면 일어나지 않았습니다. 서로 다른 두 광장 사이에는 같은 방향의 도로가 최대 하나만 존재합니다.

싸움이 표시된 도로들에서만 정확히 일어나도록 하는 움직임 순서가 존재하지 않으면 $-1$을 출력합니다.

그렇지 않으면 한 줄에, 유효한 순서 중 사전순으로 가장 앞서는 것을 출력합니다. 즉 $1$부터 $n$까지의 순열 $P_1\ P_2\ \dots\ P_n$을 공백 하나로 구분하여 출력하며, 이는 광장 $P_1$의 그룹이 가장 먼저, 그다음 광장 $P_2$의 그룹, ... 순으로 움직였음을 뜻합니다. 유효한 순서가 여러 개라면 사전순으로 가장 작은 수열을 출력합니다($P_1$을 먼저 비교하고, 같으면 $P_2$를 비교하는 식).

• $2 \le n \le 20,000$
• $1 \le m \le 200,000$
• $1 \le a, b \le n$, $a \ne b$, $c \in {0, 1}$

광장 $8$개와 일방통행 도로 $9$개가 있고, 도로 $1 \to 4$, $1 \to 8$, $7 \to 4$, $7 \to 1$에서 싸움이 기록된 경우를 생각해 봅시다. 유효한 움직임 순서 중 하나는 $8, 5, 6, 2, 3, 1, 7, 4$입니다:

• 그룹 $8$이 먼저 움직여 광장 $8$을 점령합니다.
• 그룹 $5$가 광장 $5$, $6$, $4$를 점령합니다(모두 빈 광장을 통해 도달 가능).
• 그룹 $6$은 자기 광장이 이미 점령되어 있어 아무것도 하지 않습니다.
• 그룹 $2$가 광장 $2$와 $3$을 점령합니다.
• 그룹 $3$은 아무것도 하지 않습니다.
• 그룹 $1$이 광장 $1$을 점령합니다. 도로 $1 \to 4$와 $1 \to 8$은 이미 점령된 광장으로 향하므로 그곳에서 싸움이 벌어집니다.
• 그룹 $7$이 광장 $7$을 점령합니다. 도로 $7 \to 1$과 $7 \to 4$도 이미 점령된 광장으로 향하므로 그곳에서 싸움이 벌어집니다.
• 그룹 $4$는 아무것도 하지 않습니다.

이 순서는 기록된 네 싸움만 정확히 만들어 내므로 유효합니다. 이 입력에는 유효한 순서가 여러 개 있으며(예: $2, 3, 8, 4, 1, 7, 5, 6$도 유효합니다), 요구되는 답은 그중 사전순으로 가장 작은 $2\ 3\ 4\ 5\ 6\ 8\ 1\ 7$입니다. 반면 순서 $8, 5, 6, 3, 2, 1, 7, 4$는 표시되지 않은 도로 $2 \to 3$에서 싸움을 만들어 내므로 유효하지 않습니다.