← 返回题目列表

AtCoder · tessoku_book_bu

A73. 马拉松路线

中文机器翻译题面 查看原题

配点: 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