Description

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

Format

Input

第一行为两个整数 n，m。N 为旅游的目的地城市编号，同时也是城市的个数。m 表示以下有 m 条城市间的旅行信息，每条信息为三个整数 i j w，表示从城市 i 到城市 j 需要的费用为 w（注意从城市 j 到城市 i 的费用也是 w）。
其中 2<=n<=100，1<=m<=200，0<=w<=1000。总保证旅游路线是存在的。

Output

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

Sample 1

Input

3 2
1 2 100
2 3 200

Output

100

Limitation

1s, 128MiB for each test case.

Hint

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

Source

2018年泉州复赛模拟普及组 day2t2