正则表达式(Regular Expression)

题目描述

小 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$。

输出格式

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

样例输入 #1

3 2
1 2 1
2 3 1

样例输出 #1

2

样例输入 #2

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

样例输出 #2

3

数据范围

• 对于 $40\%$ 的数据，$1\leq n\leq 10^3$, $1\leq m\leq 10^4$；
• 对于 $70\%$ 的数据，$1\leq n\leq 5 \times 10^3$， $1\leq m\leq 10^5$；
• 对于 $100\%$ 的数据，$1\leq n\leq 2 \times 10^5$， $1\leq m\leq 10^6$。

保证答案在 int 范围内。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1750。

测试点分布

出处：原题链接