Problem
다음 여름 컴퓨터 학교를 위해 학생과 모든 교사를 위한 서클을 준비하기로 결정했습니다.
디자이너는 중요한 일을 마지막 순간에 처리하는 버릇이 있어 학교 시작 이틀 전에 레이아웃을 완성했습니다. 제조업체가 머그잔을 만들고 그 위에 이미지를 넣는 데는 하루가 더 걸립니다. NATO가 머그잔을 공장에서 LKSH로 가져가는 데 24시간밖에 걸리지 않습니다.
10,000,000개의 머그(즉, 주최자가 주문한 수량)에 대한 주문은 물론 한 번에 취소할 수 없습니다. 그러나 첫 번째 비행에는 최대 머그잔 수를 가져오고 싶습니다. 운송을 위해 대형 트럭 한 대가 주문되었습니다. 그러나 한 가지 주의 사항이 있습니다. 일부 도로에서는 차량 중량에 제한이 있습니다. 따라서 차에 머그컵이 안구까지 실려 있으면 최단 경로를 사용하지 못할 수도 있지만 우회해야합니다. 이로 인해 트럭이 정시에 캠프에 도착할 시간이 없어 허용되지 않을 수도 있습니다. 그렇다면 도로 규칙을 위반하지 않고 제 시간에 이 귀중한 화물을 가져올 시간을 갖기 위해 얼마나 많은 머그잔을 차에 실을 수 있을까요?
입력
첫 번째 줄에는 숫자 n(1≤n≤500)과 도로 지도의 노드 수인 m이 각각 포함됩니다. 다음 m 행에는 도로에 대한 정보가 포함됩니다. 각 도로는 다음과 같이 별도의 줄에 설명되어 있습니다. 먼저 이 도로로 연결된 교차점의 수, 이 도로를 따라 이동하는 데 걸리는 시간, 마지막으로 이 도로에서 주행할 수 있는 차량의 최대 중량이 주어집니다. 모든 도로는 서로 다른 지점을 연결하고 각 지점 쌍에 대해 이들을 직접 연결하는 도로는 기껏해야 하나입니다. 모든 숫자는 하나 이상의 공백으로 구분됩니다.
노달 포인트는 1에서 n까지 번호가 매겨집니다. 동시에 머그잔 생산 공장에는 1 번과 LKSH-번호 n이 있습니다. 도로 이동 시간은 분 단위로 표시되며 1440(24시간)을 초과하지 않습니다. 질량 한계는 그램으로 표시되며 10억을 초과하지 않습니다. 또한 머그 하나의 무게는 100g, 빈 트럭은 - 3톤.
출력
단일 숫자 인쇄 - 24시간을 초과하지 않는 첫 비행에 가져올 수 있는 최대 머그 수.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2 |