Problem
어트랙션 "지식의 미로"는 여름 컴퓨터 학교(LCS)에 지어졌습니다. 미궁은 1에서 N까지 번호가 매겨진 N개의 방으로 구성되어 있으며 그 중 일부는 방 사이에 문이 있습니다. 사람이 문을 통과할 때 그의 지식 지표는 이 문에 고정된 일정량만큼 변경됩니다. 미로의 입구는 방 1, 출구 – N 방에서. 각 학생은 미로를 정확히 한 번 통과하고 얻은 지식의 양에 따라 하나 또는 다른 스터디 그룹에 들어갑니다 (미로에 들어갈 때이 지표는 0입니다). 당신의 임무는 최상의 결과를 보여주는 것입니다.
입력:
입력의 첫 번째 줄에는 정수 N(1 <= N <= 2000)이 포함됩니다. 객실 수 및 M(1 <= M <= 10000) – 문 수. 다음 M 줄 각각에는 문에 대한 설명이 포함되어 있습니다. 그것이 이어지는 방의 수(한 방향으로만 문을 통과할 수 있음)와 문을 통과할 때 지식의 양에 추가되는 정수(이 숫자는 모듈로에서 10000 초과). 문은 한 방에서 다른 방으로 통할 수 있고, 두 방 사이에 문이 두 개 이상 있을 수 있습니다.
출력:
":)" 표시 – 무제한의 지식을 얻을 수 있다면 ":(– 미궁을 통과할 수 없는 경우 – 그렇지 않으면 얻을 수 있는 지식의 최대치.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
2 2
1 2 3
1 2 7
|
7 |