#P2169. 正则表达式

正则表达式

题目背景

小Z童鞋一日意外的看到小X写了一个正则表达式的高级程序,这个正则表达式程序仅仅由字符“0”,“1”,“.”和“*”构成,但是他能够匹配出所有在OJ上都AC的程序的核心代码!小Z大为颇感好奇,于是他决定入侵小X的电脑上去获得这个正则表达式的高级程序。

题目描述

在Internet网络中的每台电脑并不是直接一对一连通的,而是某些电脑之间存在单向的网络连接,也就是说存在A到B的连接不一定存在B到A的连接,并且有些连接传输速度很快,有些则很慢,所以不同连接传输所花的时间是有大有小的。另外,如果存在A到B的连接的同时也存在B到A的连接的话,那么A和B实际上处于同一局域网内,可以通过本地传输,这样花费的传输时间为0。

现在小Z告诉你整个网络的构成情况,他希望知道从他的电脑(编号为1),到小X的电脑(编号为n)所需要的最短传输时间。

输入格式

第一行两个整数n, m, 表示有n台电脑,m个连接关系。

接下来m行,每行三个整数u,v,w;表示从电脑u到电脑v传输信息的时间为w。

输出格式

输出文件仅一行为最短传输时间。

3 2
1 2 1
2 3 1
2
5 5
1 2 1
2 3 6
3 4 1
4 2 1
3 5 2
3

提示

对于 40%40\% 的数据, 1n1031\leq n\leq 10^3, 1m1041\leq m\leq 10^4

对于 70%70\% 的数据, 1n5×1031\leq n\leq 5 \times 10^31m1051\leq m\leq 10^5

对于 100%100\% 的数据, 1n2×1051\leq n\leq 2 \times 10^51m1061\leq m\leq 10^6