Description

假期就要到来了，住在城市编号为$1$ 的小胖也开始在为他的旅游做准备，并 不富裕的他选择了消费水平最低的编号为$n$ 的城市作为旅游的目的地。就在他预 定完整旅游路线时，旅游公司为回报小胖多年来对他们公司的支持，特别地为他 提供了一个优惠条件：他所选的旅游路线中最贵的一次旅行将是免费的（一次旅 行是指从一个城市到另一个城市）。

给你各个城市之间的旅行费用，请帮他预定一条花费最少的旅游路线。

Input Format

第一行为两个整数$n$，$m$。

$N$ 为旅游的目的地城市编号，同时也是城市的个数。$m$ 表示以下有$m$ 条城市 间的旅行信息，每条信息为三个整数$i$ $j$ $w$，表示从城市$i$ 到城市$j$ 需要的费用 为$w$（注意从城市$j$ 到城市$i$ 的费用也是$w$）。

其中2<=$n$<=100，1<=$m$<=200，0<=$w$<=1000。总保证旅游路线是存在的。

Output Format

一个整数，表示最少的旅游费用。

Sample

输入样例

3 2
1 2 100
2 3 200

输出样例

100

样例解释

样例数据显然只有一条旅游路线：$1$->$2$->$3$。原始费用为$100+200$，优惠后 为$100$。故结果为$100$。

Hint

不要用标程，标程过不了