27934번 - 마계안암 서브태스크

문제

태윤이는 연세대학교 과잠을 입고 안암 곳곳을 여행하려고 한다.

안암은 $N$개의 건물과 서로 다른 건물들을 잇는 $M$개의 길로 나타낼 수 있다. 안암역은 1ドル$번 건물이고, 태윤이는 현재 안암역에 있다. 모든 길은 일방통행이고, 0명 이상의 고려대학교 학생들이 존재한다.

태윤이가 어떤 길을 지나가기 위해서는 그 길에 존재하는 고려대학교 학생들의 수만큼 연세빵을 바치고 이동해야 한다. 태윤이는 최소한의 빵을 빼앗기고 안암을 여행하고 싶기 때문에, 안암역에서 시작해서 각각의 건물로 최소한의 빵을 빼앗기고 도달하는 서로 다른 경로의 수를 구하려고 한다. 경로란 안암역에서 출발해 건물에 도착할 때까지 지나간 길들을 순서대로 나열한 것이다. 이때 같은 길을 여러 번 지나갈 수 있다.

안암역에서 시작해서 각 건물까지 최소한으로 빵을 빼앗기고 도착하는 서로 다른 경로의 수를 구해보자. 안암역에서 모든 건물로 도착할 수 있음이 보장된다.

입력

건물의 개수 $N$이 주어진다. 이어 길의 개수 $M$이 주어진다.

이어 $M$줄에 걸쳐 $i$번째 길의 정보가 $u_i$ $v_i$ $w_i$의 형식으로 주어진다. $i$번째 길을 통해 $u_i$번 건물에서 $v_i$번 건물로 이동할 수 있고, 길에는 $w_i$명의 고려대학교 학생이 존재한다는 뜻이다.

출력

$N$줄에 걸쳐 각 건물에 최소한으로 빵을 빼앗기고 도착하는 서로 다른 경로의 수를 출력한다. 만약 그러한 경로가 무수히 많다면 -1을 출력한다.

경로가 무수히 많지 않은 경우에, 경로의 수가 매우 클 수 있으므로 998ドル,244円,353円$로 나눈 나머지를 출력한다.

제한

• 1ドル \leq N \leq 100,000円$
• 0ドル \leq M \leq 200,000円$
• 0ドル\leq w_i \leq10^9$ $(1 \leq i \leq M)$
• $u_i\neq v_i$ $(1 \leq i \leq M)$

서브태스크

힌트