题目描述

有 $n$（$n\leq 50$）个城市，保证每个城市与其他城市之间必然有连接，但是两个城市之间会存在多条道路，输入道路连接的两个城市号及道路长度。

同时在夜晚，某些道路会封路。请输出在白天和夜晚从城市 $1$ 到城市 $n$ 之间的最短路径。

输入格式