題目描述

輸入格式

輸入的第 1 行包含一個正整數 n ( n ≤ 5 x 10⁴ )

輸入的第 2 行包含一個正整數 m ( m ≤ 10⁵ )

輸入的第 3 行包含一個正整數 root ( root ≤ 5 x 10⁴)

輸入的第 4 行至 3+m 行包含 3 個正整數 v_i, u_i, t_i ( v_i ≤ 5 x 10⁴, u_i ≤ 5 x 10⁴, t_i ≤ 10⁶, u_i v_{i )}

輸出格式

輸出只有一行，包含一個正整數 ans , 表示最優的樹結構流水綫所耗時 T_max

Samples

4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2

4

原始資料

• Zero1 題號：a363
• Hydro 題號：Z0363
• Locale：zh_TW
• Display：open