마계안암

면접 대비

시간 제한2초메모리 제한1024 MB

요약

각 건물에 대해 건물 1에서 최소 비용으로 도달하는 경로의 수를 구합니다. 비용이 0인 사이클로 경로가 무한히 많아지면 -1을 출력합니다.

난이도: 보통10점 중 6점
유형: 최단 경로, 그래프, 동적 계획법, DFS
정답자: 아직 제출이 없습니다

문제

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

안암은 $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 \leq 10^9$ $(1 \leq i \leq M)$
$u_i \neq v_i$ $(1 \leq i \leq M)$

예제3

예제 1
입력
```
4 4
1 2 2
1 3 3
2 3 1
3 4 4
```
예상 출력
```
1
1
2
2
```

예제 2

입력

예상 출력

예제 3
입력
```
3 3
1 3 0
1 2 3
3 1 0
```
예상 출력
```
-1
-1
-1
```