좋은 게임을 만드는 방법

ICPC(International Company for Playing and Competing)라는 비디오 게임 회사가 새로운 아케이드 게임을 개발하고 있다. 이 게임에는 분기가 많다. 덕분에 플레이어는 자신의 실력에 따라 경로를 선택할 수 있어 누구나 즐길 수 있다. 초보자는 쉬운 경로를 골라 게임을 즐기고, 실력 있는 플레이어는 좋아하는 경로를 골라 높은 점수를 얻는다.

게임에는 경로로 연결된 많은 체크포인트가 있다. 각 경로는 여러 스테이지로 이루어져 있고, 경로의 스테이지를 모두 완료하면 다음 체크포인트로 이동한다. 특정 체크포인트에 도달하면 게임이 끝난다. 일부 체크포인트에서는 어느 쪽으로 갈지 선택할 수 있어 경로가 갈라진다. 때로는 서로 다른 경로가 하나의 체크포인트에서 합쳐지기도 한다. 체크포인트 사이의 경로에는 방향이 있고 순환이 없다. 순환이 있다면 플레이어가 게임을 영원히 플레이할 수 있기 때문이다. 즉, 체크포인트 사이의 경로를 방향 간선으로 보면 게임의 구조는 DAG(방향 비순환 그래프)이다.

최근 개발팀은 게임의 베타 버전을 완성하고 다른 팀의 피드백을 받았다. 전반적으로 긍정적이었지만 고려해야 할 의견도 있었다. 일부 테스터는 어떤 경로가 가장 긴 경로에 비해 매우 짧다고 지적했다. 실제로 베타 버전에서는 한 번의 플레이에서 스테이지 수가 경로에 따라 크게 달라질 수 있었다. 게임 디자이너들은 촉박한 개발 일정 때문에 자신의 훌륭한 아이디어가 베타 버전에 쓰이지 못했다고 불평했다. 그들은 최종 제품에 더 많은 스테이지를 넣고 싶어 했다.

하지만 스테이지를 더 추가하는 일은 쉽지 않다. 아케이드 게임이기 때문에 플레이 시간이 너무 길면 게임의 수익이 줄고 아케이드 운영자가 불만을 제기할 수 있다. 따라서 최종 제품의 가장 긴 경로는 베타 버전의 가장 긴 경로보다 길 수 없다. 게다가 제작자는 경로 구조, 즉 체크포인트가 서로 어떻게 연결되는지를 바꾸고 싶어 하지 않았다. 시나리오를 다시 쓰고, 목소리를 녹음하고, 새로운 컷신을 만들어야 하기 때문이다.

이 모든 점을 고려해 제작자는 한 번의 플레이에서 가능한 최대 스테이지 수와 경로 구조를 그대로 유지하면서 스테이지를 최대한 많이 추가하기로 했다. 게임에 추가할 수 있는 새로운 스테이지는 몇 개인가?

N M
x1 y1 s1
.
.
.
xM yM sM

첫 줄에는 두 양의 정수 N과 M이 주어진다(2 ≤ N ≤ 100, 1 ≤ M ≤ 1000). N은 게임의 시작과 끝을 포함한 체크포인트의 수다. M은 체크포인트 사이의 경로 수다.

다음 M개 줄에는 베타 버전 게임의 경로 구조가 주어진다. i번째 줄에는 세 정수 xi, yi, si가 주어진다(0 ≤ xi < yi ≤ N - 1, 1 ≤ si ≤ 1000). 이는 체크포인트 xi에서 yi로 가는 경로가 있고 si개의 스테이지로 이루어져 있음을 나타낸다. 체크포인트의 인덱스에서 0은 게임의 시작, N - 1은 게임의 끝을 나타낸다. 모든 체크포인트 i에 대해 시작에서 끝으로 가면서 체크포인트 i를 지나는 경로가 존재한다고 가정할 수 있다. 또한 같은 두 체크포인트를 연결하는 경로는 두 개 이상 존재하지 않는다고 가정할 수 있다.

다음 제약 조건 아래에서 게임에 추가할 수 있는 새로운 스테이지의 최대 개수를 한 줄에 출력한다.

• 한 번의 플레이에서 가능한 최대 스테이지 수, 즉 끝까지 가는 가장 긴 경로의 길이를 늘릴 수 없다.
• 경로 구조, 즉 체크포인트가 서로 어떻게 연결되는지를 바꿀 수 없다.
• 베타 버전에 이미 존재하는 스테이지를 삭제할 수 없다.