问题描述

塔子哥是一位热衷旅游的程序员。他所在的国家共有 $n$ 个城市,编号从 $1$ 到 $n$。这些城市之间有 $m$ 条双向的交通线路,分别为飞机线路和火车线路。塔子哥起始位于编号为 $1$ 的城市,他计划前往编号为 $n$ 的城市进行旅游。

在这个国家,每个城市都有一个固定的时间 $a_i$,表示在该城市中转换交通工具所需的时间。特别地,在出发城市 $1$ 和目的地城市 $n$,塔子哥不需要转换交通工具。