시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 1536 MB 15 6 5 71.429%

문제

메시는 운전 브이로그를 BOJ티비에 올려 유명해지려고 한다. 메시가 사는 도시는 $n$개의 건물과 $m$개의 일방통행 도로로 이루어져 있다. 메시가 촬영을 시작하면 메시의 팬들이 몰려들기 때문에, 메시가 촬영을 시작한 후 $T$시간 뒤에 $i$번 도로에 진입하면 그 도로를 지나가는데 $T+C_i$시간이 걸린다.

메시는 $n^2$개의 영상을 촬영할 예정이다. $(i-1)n+j$번째 영상은 $i$번 건물에서 출발하여 정확히 $j$개의 도로를 지나 메시의 집인 $n$번 건물에 도착하는 영상이다. $(1 \le i, j \le n)$ 하나의 영상에서 동일한 도로를 여러 번 지날 수도 있으며, $n$번 건물에 도착했다고 해서 촬영을 끝낼 필요는 없다. 메시는 빨리 촬영을 끝내고 싶어서 조건을 만족하는 경로 중 가장 빠른 경로를 사용할 것이다. 만약 그러한 경로가 없다면, 운전 브이로그 대신 사과문 영상이 올라가게 될 것이다.

메시가 촬영한 $n^2$개의 영상을 BOJ티비에 올리면, 팬들이 각 영상에 좋아요나 싫어요를 달게 된다. $T$시간짜리 운전 브이로그 영상에는 $T$를 $10^9+7$로 나눈 나머지만큼의 좋아요가 달린다. 사과문에는 싫어요가 $1$개 달린다. 메시가 사는 도시의 모습을 보고 메시가 총 몇 개의 좋아요와 싫어요를 받게 될지 계산해보자.

입력

입력의 첫 줄에 정수 $n, m$이 주어진다.

이후 $m$개의 줄에 걸쳐 정수 $A_i, B_i, C_i$가 주어진다. $i$번 도로는 $A_i$번 건물에서 $B_i$번 건물으로 가는 도로이다. $(1 \le i \le m)$

출력

첫째 줄에 메시가 받을 (좋아요의 개수) - (싫어요의 개수)를 출력한다.

제한

  • $1 \le n \le 3\,000$
  • $0 \le m \le 10\,000$
  • $1 \le A_i, B_i \le n$ $(1 \le i \le m)$
  • $0 \le C_i \le 10^{8}$ $(1 \le i \le m)$

예제 입력 1

4 6
1 2 1
1 3 0
2 3 2
3 1 5
2 4 2
3 4 3

예제 출력 1

155

1, 7, 10, 13, 14, 15, 16번째 영상에는 각각 싫어요가 1개 달린다.

2번째 영상은 1 → 3 → 4를 운전하는 영상으로, 좋아요가 3개 달린다.

3번째 영상은 1 → 2 → 3 → 4를 운전하는 영상으로, 좋아요가 11개 달린다.

4번째 영상은 1 → 3 → 1 → 3 → 4를 운전하는 영상으로, 좋아요가 23개 달린다.

5번째 영상은 2 → 4를 운전하는 영상으로, 좋아요가 2개 달린다.

6번째 영상은 2 → 3 → 4를 운전하는 영상으로, 좋아요가 7개 달린다.

8번째 영상은 2 → 3 → 1 → 3 → 4를 운전하는 영상으로, 좋아요가 39개 달린다.

9번째 영상은 3 → 4를 운전하는 영상으로, 좋아요가 3개 달린다.

11번째 영상은 3 → 1 → 3 → 4를 운전하는 영상으로, 좋아요가 23개 달린다.

12번째 영상은 3 → 1 → 2 → 3 → 4를 운전하는 영상으로, 좋아요가 51개 달린다.

예제 입력 2

7 6
1 2 100000000
2 3 100000000
3 4 100000000
4 5 100000000
5 6 100000000
6 7 100000000

예제 출력 2

1999999887

각 영상에 달리는 좋아요의 개수는 $10^9+7$ 미만이지만, $n^2$개의 영상을 합치면 $10^9+7$ 이상일 수도 있다.

예제 입력 3

1000 0

예제 출력 3

-1000000

$n^2$개의 영상이 모두 사과문이다.

출처

Contest > IDTcup > 제 3회 IDTcup B번