Input file name: standard input

Output file name: standard output

Time limit: 1 s

Memory limit: 1024 MB

Дядя Беня — очень известный (в узких кругах, конечно) манипулятор. Совсем недавно в его руки попалась очень интересная карта конкурирующей компании. На ней были нанесены n городов, а также m однонаправленных дорог. Карта была построена таким образом, что не найдется такой пары городов a и b, что существует простой путь из вершины a в вершину b, а также из вершины b в вершину a. На карте, помимо городов и дорог, был выписан маршрут поставки некоторого груза из города под номером 1 в город под номером n. Дядя Беня решил избавиться от конкурентов, изменив этот маршрут так, чтобы его стоимость была максимальной, тем самым причинив конкурентам большие убытки. Так как дядя Беня очень серьезный человек, он просит вас найти стоимость максимального пути.

Input

В первой строке задано два целых числа n и m — количество городов и количество дорог соответсвенно. В следующих m строках задано по три целых числа a_i, b_i​ и w_i​ — город из которого исходит дорога, город, в который дорога входит и стоимость дороги соответсвенно.

1 <= n, m <= 2*10⁹

1 <= a_i, b_i <= n

1 <= w_i <= 10⁹

Гарантируется, что путь из вершины 1 в вершину n существует всегда.

Output

В единственной строке выведие одно целое число — ответ на задачу.