[編程|1000分] 你的城市
時(shí)間限制：C/C++ 1秒欺冀，其他語言 2秒
空間限制：C/C++ 262144K蹂窖，其他語言 524288K
64bit IO Format: %lld
題目描述
2018年第一季度夜矗，美團(tuán)旅行的酒店業(yè)務(wù)以5770萬的訂單總量，成為行業(yè)第一名绵脯。
與此同時(shí)拧揽，美團(tuán)旅行也提供機(jī)票、火車票灶挟、船票等各種服務(wù)琉朽，不斷開辟新的目的旅游城市。最近新開的目的地稚铣，就包括對小A有特殊意義的偏僻小城C箱叁。
“我來到 你的城市 熟悉的那一條街√枰剑”小A哼著歌耕漱，從北京出發(fā)，要去C城抬伺。這對他非常重要螟够，必須當(dāng)天到達(dá)，雖然交通并不是非常方便峡钓。
但是妓笙，錯(cuò)過火車并不是一個(gè)小概率事件。為了保險(xiǎn)起見能岩，小A決定選擇一個(gè)即使錯(cuò)過火車也存在補(bǔ)救措施的交通方案寞宫。（即假使未趕上原方案中的任何一班火車，依然可以改乘其他的車次能夠在當(dāng)天到達(dá)C城捧灰，但同時(shí)小A是一個(gè)樂觀主義者淆九，所以他認(rèn)為改乘以后的所有車次都不會延誤。）當(dāng)然了毛俏，在滿足上述條件的情況下炭庙，小A希望花費(fèi)的錢越少越好（只考慮計(jì)劃中的，不考慮發(fā)生意外時(shí)換乘帶來的代價(jià)）煌寇。
城市及交通網(wǎng)可以看做一張n個(gè)點(diǎn)m條邊的有向圖焕蹄。每個(gè)點(diǎn)代表一個(gè)城市（1號點(diǎn)代表北京，n號點(diǎn)代表C城）阀溶。每條邊由一個(gè)五元組<x, y, c, ts, td>組成腻脏，表示存在一個(gè)車次鸦泳，由ts時(shí)刻從城市x出發(fā)，在td時(shí)刻到達(dá)城市y永品，且花費(fèi)為c元做鹰。
為了簡化問題，ts鼎姐，td均為以半小時(shí)為基本單位（具體格式見樣例及Hint）钾麸。并假設(shè)每次中轉(zhuǎn)最少需要花費(fèi)半個(gè)小時(shí)，且中轉(zhuǎn)只能發(fā)生在同一城市（即到達(dá)一個(gè)城市距離再次從這個(gè)城市出發(fā)至少需要間隔半個(gè)小時(shí)）炕桨，注意饭尝，小 A 如果因?yàn)闆]趕上車次需要改乘，也需要半個(gè)小時(shí)的時(shí)間献宫。
問小A到達(dá)C城最少需要花費(fèi)多少錢（行程必須在這一天內(nèi)完成钥平，可以在0:00上車，也可以在24:00到達(dá)）姊途。
輸入描述:
第一行涉瘾，兩個(gè)正整數(shù)n, m。n表示城市數(shù)量吭净，m表示當(dāng)天不同班次的火車數(shù)量睡汹。
接下來m行，每行3個(gè)整數(shù)x, y, c加兩個(gè)字符串ts, td寂殉，均以空格作為分隔，表示當(dāng)天的某一班火車原在。其中x, y, c, ts, td的含義如前描述友扰。
所有的車次都是當(dāng)天的，沒有隔夜的票庶柿。
2 <= n <= 500, m <= 15000, c <= 1000, ts < td村怪，所有數(shù)均為正整數(shù)。
車次保證不過夜浮庐，時(shí)間范圍0:00, 0:30, 1:00, … , 23:00, 23:30, 24:00甚负，可能存在重復(fù)車次。
輸出描述:
一個(gè)整數(shù)审残，表示存在補(bǔ)救措施的前提下梭域，小A到達(dá)C城的最小花費(fèi)。如果不存在這樣的路徑搅轿，則輸出-1病涨。
示例1
輸入
3 5
1 3 800 18:00 21:00
1 2 650 13:30 14:00
2 3 100 14:00 18:00
2 3 300 14:30 19:00
2 3 200 15:00 19:30
輸出
950
說明
選擇第二個(gè)和第四個(gè)車次。
第三個(gè)車次由于中轉(zhuǎn)時(shí)間太短無法選擇璧坟。第五個(gè)車次由于沒有可改乘的航班無法選擇既穆。
如果錯(cuò)過第二個(gè)車次赎懦，可以改乘第一個(gè)車次。如果錯(cuò)過第四個(gè)車次幻工，可以改乘第五個(gè)車次励两。
示例2
輸入
3 5
1 2 1000 0:00 12:00
1 2 100 0:30 14:00
1 2 100 0:30 15:00
2 3 300 16:00 24:00
2 3 200 16:30 24:00
輸出
1300
說明
選擇第一個(gè)和第四個(gè)車次。
不能選擇第二個(gè)車次是因?yàn)槟衣绻e(cuò)過了0:30的車次2伐蒋，那么同樣在0:30出發(fā)的車次3也是來不及改乘的。
示例3
輸入
3 4
1 2 100 0:30 14:00
1 2 200 0:30 15:00
2 3 300 16:00 24:00
2 3 200 16:30 24:00
輸出
-1
說明
和樣例二類似迁酸，但是缺少了原先的車次一先鱼，所以沒有換乘方案。
示例4
輸入
3 4
1 2 100 0:30 14:00
1 2 200 1:00 16:00
2 3 300 16:00 24:00
2 3 200 16:30 24:00
輸出
400
說明
選擇第一個(gè)和第三個(gè)車次奸鬓。
示例5
輸入
3 4
1 2 100 0:30 14:00
1 2 200 1:00 16:30
2 3 300 16:00 24:00
2 3 200 16:30 24:00
輸出
-1
說明
和樣例四類似焙畔，但假如錯(cuò)過了第一個(gè)車次，改乘車次二在16:30到達(dá)城市2是不足以趕上16:30出發(fā)的車次四的串远。