Một con bò từ mỗi trang trại trong $N$ trang trại ($1 \le N \le 1000$), được đánh số $1..N$, sẽ dự tiệc bò lớn tại trang trại $X$ ($1 \le X \le N$). Tổng cộng có $M$ ($1 \le M \le 100,000$) đường một chiều nối các cặp trang trại; đi qua đường $i$ cần $T_i$ ($1 \le T_i \le 100$) đơn vị thời gian.

Mỗi con bò phải đi bộ đến bữa tiệc, rồi trở về trang trại của mình khi tiệc kết thúc. Mỗi con đều lười nên chọn tuyến đường tối ưu có thời gian ngắn nhất. Vì các đường là một chiều, tuyến đường về có thể khác tuyến đường đi.

Trong tất cả các con bò, thời gian dài nhất mà một con phải dành để đi bộ đến bữa tiệc và trở về là bao nhiêu?

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn.

• Dòng 1: ba số nguyên cách nhau bởi dấu cách, lần lượt là $N$, $M$ và $X$.

Các dòng $2..M+1$: dòng $i+1$ mô tả đường $i$ bằng ba số nguyên cách nhau bởi dấu cách: $A_i$, $B_i$ và $T_i$. Đường đi từ trang trại $A_i$ đến trang trại $B_i$ và cần $T_i$ đơn vị thời gian để đi qua.

Dữ liệu ra

Ghi dữ liệu ra đầu ra chuẩn.

• Dòng 1: một số nguyên, là thời gian đi bộ lớn nhất của một con bò.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

10

Ghi chú

Bò $4$ đi thẳng đến bữa tiệc ($3$ đơn vị) và trở về qua các trang trại $1$ và $3$ ($7$ đơn vị), tổng cộng $10$ đơn vị thời gian.

Nguồn bài toán: USACO 2007 February Silver