配点: 1000 点
注意
根据书籍的版本,书中的代码可能不正确。请参阅勘误表。
問題文
ALGO 城有 N 交叉路口和 M 有一条真正的路。i 主路是一个十字路口 A_i 和交叉路口 B_i 双向绑扎,长度为 C_i 米。保证可以通过多条道路穿越交叉路口。另外, 在 D_i = 1 的道路上种植了一棵树。
ALGO市市长二郎在十字路口。 我决定创建一个连接 1 和交叉路口 N 的马拉松课程。他希望总距离尽可能短,因为他不想让参与者感到疲劳。我们也希望参与者能够享受大自然,所以如果总距离相同,我们希望增加球场上种植的树木数量。您心目中的马拉松课程是什么样的?
制約
- 2 \leq N \leq 8{,}000
- 1 \leq M \leq 100{,}000
- 1 \leq C_i \leq 100
- 保证可通过多条道路到达交叉路口。
- 1 \leq A_i < B_i \leq N
- i \neq j 如果 (A_i, B_i) \neq (A_j, B_j)
- D_i 是 您也可以写 0 或 至少 1 是
入力
输入是按以下格式从标准输入给出的。
N M A_1 B_1 C_1 D_1 \vdots A_M B_M C_M D_M
出力
请输出马拉松赛道的总距离以及赛道上树木的数量,以空格分隔。
入力例 1
3 3 1 2 70 1 2 3 20 1 1 3 90 0
出力例 1
90 2