Ваше завдання — знайти маршрут від міста A до міста B за мінімальною ціною. У вас є один дисконтний купон, скориставшись яким ви можете вдвічі знизити ціну будь-якого окремого рейсу на маршруті. Однак скористатися купоном можна лише один раз.

Коли ви використовуєте купон на знижку на рейс, ціна якого дорівнює \(x\), його ціна стає \(\lfloor x/2 \rfloor\) (вона округлюється до цілого числа).

Обмеження

• \(2 \le n \le 10^5\)
• \(1 \le m \le 2 \cdot 10^5\)
• \(1 \le a,b \le n\)
• \(1 \le c \le 10^9\)

Формат вхідних даних

У першому рядку вводу два цілих числа \(n\) і \(m\): кількість міст і рейсів. Міста пронумеровані \(1,2,...,n\). Місто 1 – A, а місто \(n\) – B.

Після цього йде \(m\) рядків з описом рейсів. Кожен рядок містить три цілі числа \(a\), \(b\) і \(c\): рейс починається в місті \(a\), закінчується в місті \(b\), а його ціна дорівнює \(c\). Кожен рейс однонаправлений.

Можна припустити, що з A до B завжди можна дістатися.

Формат вихідних даних

3 4
1 2 3
2 3 1
1 3 7
2 1 5

Приклад вхідних даних

2