Within Half an Hour

By Kay Akashi

Time: 1000 ms

Memory: 256000 kB

The code judging system is only available during contests. Check out the github repo for test cases and solutions.

Please log in.

Problem Statement

Given an underground network map consisting of $n$ stations named from $1$ to $n$ , output the number of stations within $30$ minutes of walking distance from station $s$ if you choose the path optimally.

In $m$ lines, you are given $a_i$ , $b_i$ , and $c_i$ $(1 \leq i \leq m)$ , $(1 \leq a_i, b_i \leq n)$ , $(1 \leq c_i \leq 100)$ , indicating that station $a_i$ is bilaterally connected to station $b_i$ and it takes $c_i$ minute(s) to walk from one to another.

Note that, station $s$ should be counted since this can be reached in $0$ minute.

Constraints

$1 \leq n, m \leq 1000$ , $1 \leq a_i, b_i, s \leq n$ , $1 \leq c_i \leq 100$ .

Input

The first line of input contains three integers, $n$ , $m$ , and $s$ . Following are $m$ lines each of which contains three integers, $a_i$ , $b_i$ , and $c_i$ .

Output

Output the answer.

Examples

Input

Output

Explanation

Station $1$ , $2$ , $3$ , and $4$ can be accessed in $0$ , $10$ , $5$ , and $30$ minutes respectively. All stations can be reached within $30$ minutes hence the answer is $4$ .

Input

Output

Explanation

Station $1$ , $2$ , $3$ , $4$ , and $5$ can be accessed in $19$ , $0$ , $32$ , $28$ , and $31$ minutes respectively. Amongst those five stations, station $1$ , $2$ , and $4$ satisfy the condition, hence the answer is $3$ . Note that, you cannot reach station $6$ and $7$ because there's no service thus you don't count them.

Within Half an Hour

Submit Code

Previous Submissions

Problem Statement

Constraints

Input

Output

Examples

Input

Output

Explanation

Input

Output

Explanation