Given a connected, undirected graph with $n$ vertices and $m$ edges, where the weight of the $i$-th edge is denoted as $w_i$, we define the cost of a path through edges $e_1, e_2, \dots, e_k$ as:
$$k \cdot X + \sum_{i=1}^{k} w_{e_i} - \max(w_{e_1}, \dots, w_{e_k}) + \min(w_{e_1}, \dots, w_{e_k})$$
The objective is to find the path with the smallest cost from vertex $S$ to any of the remaining $n-1$ vertices.
### Input
- The first line contains four positive integers: $n$, $m$, $S$, and $X$.
- The next $m$ lines each contain three positive integers $u$, $v$, and $w$, describing an edge of the graph.
### Output
- Print $n-1$ integers, which are the required results, in order from $1$ to $n$.
### Constraints
- $1 \le n,m \le 200000, 1 \le S \le n , 1 \le X \le 10^9.$
- For the edges, $1 \le u \ne v \le n$ and $1 \le w \le 10^9$.
### Example
Input:
```
4 5 1 25
1 2 69
2 3 10
3 4 68
4 1 17
1 3 35
```
Output:
```
70 60 42
```
Input:
```
4 5 1 3
1 2 6
2 3 7
4 3 8
4 1 9
3 1 10
```
Output:
```
9 13 12
```
