

철수가 사는 동네에는 $N$ 개의 공원이 있고,
각각 두 개의 서로 다른 공원을 
양방향으로 연결하는 길들이 $M$ 개 있다. 각 길의 길이를 알고 있다고 하자.
공원들은 $1$부터 $N$까지 번호가 붙어 있다.

철수는 현재 공원 $S$에 있다. 철수는 서로 다른 두
개의 공원 $A$와 공원 $B$를 정해서
공원 $S$에서 공원 $A$로, 공원 $A$에서 공원 $B$로, 다시 공원 $B$에서 공원 $S$로
돌아오려고 한다. 모든 과정에서 전체 이동 거리가 가장 작도록 이동한다.
단, $A$와 $S$는 서로 같지 않고, $B$와 $S$도 서로 같지 않다.

위의 과정에서 같은 공원을 여러 번 지나는 것은 허용되지만, 중간에 공원 $S$를 
지나는 것은 허용되지 않는다.

가능한 $A$와 $B$를 정하는 모든 방법에 대해서 전체 이동 거리가 가장
짧은 것을 찾아 그 길이를 출력하는 프로그램을 작성하시오.

아래 그림은 입력 예제의 경우를 보여 준다. $A = 3$, $B = 6$으로 정하면
총 $10$의 거리를 이동하여 위의 조건을 만족할 수 있다.


![사진](https://s3.ap-northeast-2.amazonaws.com/bikoprodweb-static-production/problem/121/statement/images/191b31f23d35fead16cd)


## 입력 형식

첫 줄에 공원의 수와 길의 수, 현재 공원의 번호를 나타내는
세 정수 $N$, $M$, $S$가 공백으로 구분되어 주어진다.
($3 \le N \le 100\,000;$ $3 \le M \le 200\,000;$ $1 \le S \le N$)

이어지는 $M$ 개의 줄의 각 줄에 길의 정보를 나타내는
세 정수 $a$, $b$, $c$가 공백으로 구분되어 주어진다.
($1 \le a, b \le N;$ $1 \le c \le 1\,000\,000\,000;$ $a \ne b$)

이는 공원 $a$와 공원 $b$ 사이를 양방향으로 연결하는 길이 $c$인 길이 존재함을 의미한다.

답이 불가능한 경우는 입력으로 주어지지 않는다.

## 출력 형식

첫 줄에 답이 되는 정수를 출력한다.

## 입력 예제

```
6 10 5
1 4 2
2 1 2
4 6 10
1 4 4
4 3 8
4 5 9
3 4 9
5 6 3
3 6 2
1 4 1
```

## 출력 예제

```
10
```

## 채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 
그 종류에 배정된 점수를 받을 수 있다.

* 종류 1 (32점): $N \le 300;$ $M \le 1\,000$
* 종류 2 (24점): $N \le 3\,000;$ $M \le 6\,000$
* 종류 3 (44점): 추가적인 제한 조건이 없음.
