전기차 랠리

전기차가 쓸 만하다는 것을 보이려고 ElecCarCo가 전국을 도는 도로 랠리를 후원한다. 코스에는 충전소가 $n$개 있고 번호는 $0$번부터 $n-1$번까지다. 차는 어느 충전소에서든 멈춰 배터리를 충전한다.

랠리는 며칠씩 이어지기도 한다. 완충한 배터리로는 $240$분을 달릴 수 있고, $1$분을 달리려면 충전기에 $2$분을 꽂아 두어야 한다. 충전량은 꽂아 둔 시간에 비례해 쌓여서, $w$분을 꽂아 두면 달릴 수 있는 시간이 $w/2$분 늘고 상한은 $240$분이다. 모든 차는 첫날 정오에 배터리를 가득 채우고 출발한다. 배터리를 다 채운 뒤에도 차는 충전소에 얼마든지 머무를 수 있다. 남은 주행 시간이 어떤 도로의 주행 시간보다 짧으면 그 도로에는 들어설 수 없다.

도로는 정해진 충전소 쌍 사이에만 놓여 있다. 교통량, 노면 상태, 전용 차로 운영 같은 조건 때문에 같은 도로라도 들어서는 시각에 따라 주행 시간이 달라진다. 도로는 모두 양방향이고, 두 방향 모두 같은 조건을 따른다.

$0$번 충전소에서 출발해 $n-1$번 충전소에 가장 먼저 닿는 차가 우승한다. 출발지와 도착지 말고는 제약이 없어서, 중간 충전소는 어떤 순서로 지나도 되고 모든 충전소를 들르지 않아도 된다.

차가 마지막 충전소에 닿을 수 있는 가장 이른 시각을 랠리 시작 이후 흐른 분 수로 구하는 프로그램을 작성하시오.

입력에는 테스트 케이스가 여러 개 들어 있다. 각 테스트 케이스의 첫 줄에는 충전소의 수 $n$ ($1 \le n \le 500$)과 도로 구간의 수 $m$ ($1 \le m \le 1000$)이 주어진다.

이어서 도로 구간 하나를 설명하는 블록이 $m$개 온다. 블록의 첫 줄에는 그 구간이 잇는 두 충전소의 번호 $a$와 $b$ ($0 \le a, b \le n-1$, $a \ne b$)가 주어진다. 구간에는 방향이 없어서 $a$에서 $b$로도, $b$에서 $a$로도 달릴 수 있다.

그다음에는 주행 시간을 알려 주는 줄이 $1$개 이상 $20$개 이하로 온다. 각 줄에는 정수 세 개 Start, Stop ($0 \le \text{Start} < \text{Stop} \le 1439$), Time ($0 < \text{Time} < 1000$)이 있다. Start와 Stop은 자정부터 잰 하루 안의 시각이고, Time은 $[\text{Start}, \text{Stop}]$ 안의 어느 시각에 이 구간으로 들어섰을 때 걸리는 주행 시간이다. 블록의 첫 줄은 Start가 $0$이고 마지막 줄은 Stop이 $1439$다. 줄은 시각 순서대로 오고 둘째 줄부터는 Start가 바로 앞 줄의 Stop보다 $1$ 크므로, 한 블록의 줄들은 00:00부터 23:59까지 하루를 빠짐없이 덮는다.

입력의 끝에는 $0$이 두 개 적힌 줄이 온다. 모든 테스트 케이스는 차가 완주할 수 있는 코스를 담고 있다.

각 테스트 케이스마다 랠리를 마치는 데 걸리는 최소 시간을 분 단위 정수로 한 줄에 하나씩 출력한다. 다른 문자는 출력하지 않고, 답과 답 사이에 빈 줄도 넣지 않는다.