题号：NC52805
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
Special Judge, 64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
Special Judge, 64bit IO Format: %lld
题目描述
Bobo 居住在大城市 ICPCCamp。
ICPCCamp 有 n 个地铁站，用
编号。
m 段双向的地铁线路连接 n 个地铁站，其中第 i 段地铁属于
号线，位于站 
之间，往返均需要花费 
分钟（即从 
到 
需要 分钟，从 到 也需要 分钟）。
众所周知，换乘线路很麻烦。如果乘坐第 i 段地铁来到地铁站 s，又乘坐第 j 段地铁离开地铁站 s，那么需要额外花费
分钟。注意，换乘只能在地铁站内进行。
Bobo 想知道从地铁站 1 到地铁站 n 所需要花费的最小时间。
ICPCCamp 有 n 个地铁站，用
m 段双向的地铁线路连接 n 个地铁站，其中第 i 段地铁属于
众所周知，换乘线路很麻烦。如果乘坐第 i 段地铁来到地铁站 s，又乘坐第 j 段地铁离开地铁站 s，那么需要额外花费
Bobo 想知道从地铁站 1 到地铁站 n 所需要花费的最小时间。
输入描述:
输入包含不超过 20 组数据。
每组数据的第一行包含两个整数 n, m ().
接下来 m 行的第 i 行包含四个整数(
).
保证存在从地铁站 1 到 n 的地铁线路（不一定直达）。
输出描述:
对于每组数据，输出一个整数表示要求的值。