题目描述

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

格式

输入格式

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

输出格式

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

样例1

样例输入1

3 2
1 2 100
2 3 200

样例输出1

100

样例解释

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