2072: 正则表达式
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：10
解决：4
题目描述
小Z 童鞋一日意外的看到小X 写了一个正则表达式的高级程序，这个正则
表达式程序仅仅由字符“0”,“1”，“.”和“*”构成，但是他能够匹配出所有
在OJ 上都AC 的程序的核心代码！小Z 大为颇感好奇，于是他决定入侵小X 的电
脑上去获得这个正则表达式的高级程序。
在Internet 网络中的每台电脑并不是直接一对一连通的，而是某些电脑之
间存在单向的网络连接，也就是说存在A 到B 的连接不一定存在B 到A 的连接，
并且有些连接传输速度很快，有些则很慢，所以不同连接传输所花的时间是有大
有小的。另外，如果存在A 到B 的连接的同时也存在B 到A 的连接的话，那么A
和B 实际上处于同一局域网内，可以通过本地传输，这样花费的传输时间为0。
现在小Z 告诉你整个网络的构成情况，他希望知道从他的电脑（编号为1），
到小X 的电脑（编号为n）所需要的最短传输时间。
表达式程序仅仅由字符“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提示
【样例输入输出2】
regexp.in
5 5
1 2 1
2 3 6
3 4 1
4 2 1
3 5 2
regexp.out
3
【数据范围】
对于40%的数据，1<=n<=1000, 1<=m<=10000
对于70%的数据，1<=n<=5000, 1<=m<=100000
对于100%的数据，1<=n<=200000, 1<=m<=1000000