Phát biểu bài toán

Vương quốc HT có ~ N ~ thần dân sống trong ~ N ~ ngôi nhà đánh số từ ~ 1 ~ đến ~ N ~. HT muốn tổ chức một bữa tiệc tại nhà số ~ X ~. Mỗi thần dân sẽ xuất phát từ nhà mình, đi theo con đường ngắn nhất đến nhà ~ X ~, và sau đó quay về nhà mình.

Bài toán yêu cầu tính thời gian lớn nhất mà một thần dân phải bỏ ra để di chuyển từ nhà mình đến nhà ~ X ~ và quay về.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên ~ N, M, X ~:
  • ~ N ~: Số lượng ngôi nhà (~ 1 \leq N \leq 1000 ~).
  • ~ M ~: Số lượng con đường một chiều (~ 1 \leq M \leq 100,000 ~).
  • ~ X ~: Số của ngôi nhà nơi tổ chức bữa tiệc (~ 1 \leq X \leq N ~).
• ~ M ~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~ u, v, T ~:
  • ~ u, v ~: Đường một chiều từ nhà ~ u ~ đến nhà ~ v ~.
  • ~ T ~: Thời gian đi qua con đường (~ 1 \leq T \leq 100 ~).

Dữ liệu ra

• Một số duy nhất: Thời gian lớn nhất mà một thần dân phải bỏ ra để đi và về từ nhà ~ X ~.

Ví dụ

Input

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

Output

10

Giải thích:

• Nhà ~ 2 ~ là nơi tổ chức bữa tiệc.
• Các thần dân phải di chuyển đến nhà ~ 2 ~ và quay về theo thời gian tối thiểu:
  • Nhà ~ 1 ~: ~ 4 + 1 = 5 ~.
  • Nhà ~ 2 ~: ~ 0 + 0 = 0 ~ (ở sẵn tại nhà ~ 2 ~).
  • Nhà ~ 3 ~: ~ 5 + 2 = 7 ~.
  • Nhà ~ 4 ~: ~ 3 + 7 = 10 ~.
• Thần dân ở nhà ~ 4 ~ mất nhiều thời gian nhất: ~ 10 ~.