题目内容

$A$ 国与 $B$ 国是相邻的两个国家，每个国家都有很多城市，国家内部有很多连接城市的公路，国家之间也有很多跨国公路，连接两个国家的边界城市。

两个国家一共有 $N$ 个城市，编号 $1$ 到 $N$ ，一共有 $M$ 条公路，包括国内公路与跨国公路。

小塔生活在 $A$ 国的城市 $1$（即编号为$1$的城市），想去 $B$ 国的城市 $N$ 游玩，由于小塔办理的只能入境一次的签证，所以从城市 $1$ 到城市 $N$ 的路径中，只能通过一条跨国公路。

每条公路都一个距离，并且通过这条公路会有一个花费。