No submission language available for this problem.

Background

Special for beginners, ^_^

Description

Steve 要从公司搬物品到家，东西非常重，而且只能走路。为了少走一些路，他麻烦 Gold King 做一个搬家方案。

从公司到家的路上有N个路口，编号从 1–N。每两个路口之间可能有多条路线，总共有 M 条路线，每一条路线都有其对应的长度，需要从 1 号路口开始，要到达 N 号路口。

Gold King 陷入了沉思，这个搬家方案该怎么做才能让需要走的路距离最短，最短距离是多少。

Format

Input

输入第一行是两个整数 N 和 M，表示有 N 个路口，并且有 M 条路线。 接下来 M 行，每行包括 3 个整数 A，B，C，分别为 A 号路口到 B 号路口，距离是 C。

Output

输出一个整数结果，表示制定出来的方案最短距离值是多少。

Samples

2 1
1 2 3

3

3 3
1 2 5
2 3 5
3 1 2

2

Limitation

数据可能包含重边

2<=N<=100

1<=M<=3500

1<=A, B<=N

1<=C<=1000

1s, 1024KiB for each test case.