Responsive image

问题 A: 帮小白送快递

问题 A: 帮小白送快递

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 39
[提交][状态][讨论版][命题人:]

题目描述

小红的老公小白是个考古学家，有一天小白发现了只白白圆圆小小的木乃伊，它是个爱哭鬼却很努力。小白想把这么可爱的小木乃伊送给老婆，于是便找上了快递姐姐，这下可让快递姐姐犯愁了，因为去往小红家的路实在太难走了（甚至有可能没有路能走到小红家），快递姐姐找上聪明的你，想请你帮忙找出最快到达小红家的路，你行吗？

输入描述

第一行输入两个整数n和m（2<=n<=m<=200000），分别表示有n座城市和m条路，城市编号为1~n（快递姐姐所在城市为1，小红所在城市为n）。
接下来m行，每行输入3个整数u,v,w（u,v<=n，w<=100000），分别表示城市u和城市v之间有一条长为w的路。

输出描述

输出结果占一行，输出快递姐姐到达小红家最短需要走多远的路，如果没有路能走到小红家，则输出“qwb baka”（不用输出双引号）。

样例输入

4 4
1 2 1
2 3 2
3 4 3
2 3 1

样例输出

5
[提交][状态]
ACM算法攻关部