Description

小明住在城市1，今年夏天他准备要去城市n旅游。但由于他经费有限，所以他要用最小的花费到达目的地。于是他打开电脑开始查询，查到了m条信息。每条信息表示城市i到城市j的花费k(两个城市间的道路是双向的)。两个城市间可能有多种不通花费(比如坐火车和乘飞机)。小明向你求助，帮他算出他从城市1到城市n的最小花费。

Input

有多组数据。每组数据有m+1行，第一行有两个整数n(2<=n<=3000),m(1<=m<=20000)。 第二行到第m+1行每行有三个整数，分别表示两个城市和它们之间通行的花费。

Output

每组数据输出一个整数，表示小明从城市1到城市n的最小花费。如果到达不了城市n，则输出"OH,NO!"。

Sample

Input

5 5
1 3 10
1 4 3
2 3 4
2 1 5
3 5 1
4 3
1 2 3
2 3 4
1 3 10

Output

10
OH,NO!

Source: catlwwy