正则表达式

【题目描述】

小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<=n<=1000, 1<=m<=10000

对于70%的数据，1<=n<=5000, 1<=m<=100000

对于100%的数据，1<=n<=200000, 1<=m<=1000000

【来源】

在此键入。