题目描述

  近来，机票的价格猛涨，于是我们决定选择距离最短情况下价格最低的航线为最优航线。如果距离不同，选择距离最短的航线；如果距离相同，则选择价格最低的航线。

  已知，有$n$个地点，$m$条无向航线，我们想从$1$号点到达$n$号点，试求解最优航线的距离和价格。

输入格式

第一行，输入两个整数$n, m(2≤n≤10^5, 1≤m≤2 \times 10^5)$。

接下来，$m$行，每行四个整数$u, v, w, c(1≤u,v≤n; 1≤w,c≤10^5)$表示$u$、$v$之间有一条距离为$w$、价格为$c$的双向航线。

输出格式

如果可以从$1$号点到$n$号点，则在一行中输出两个整数，先后分别表示最优航线的距离和价格；否则输出$-1$。

样例

4 4
1 2 2 5
2 3 3 1
1 4 9 3
2 4 4 2

6 7

来源

2022 HGNU-SWUT暑假联合集训