You and your friend live in a city with $n$ train stations and $m$ two-way routes between them. You reside near station $S$ and commute to work near station $T$. Each of $m$ routes sells train pass so to travel conveniently, you can purchase train passes that allow unlimited use of train routes. The price of a pass matches the distance between stations, so naturally, you buy passes for the shortest path from $S$ to $T$.
Your friend lives near station $X$ and commutes to work near station $Y$. Sometimes, they borrow your passes. To minimize their expenses on routes not covered by your passes, find the optimal way to purchase passes from $S$ to $T$.
### Input
- The first line contains two integers $n,m$.
- The second line contains four integers $S,T,X,Y$.
- The next $m$ lines, each line contains three integers, $u,v,w$, there is a route of length $w$ between $u$ and $v$, it also costs $w$ to buy a pass.
- Test data guaranteed that a station is reachable from any station.
### Output
- Print the minimum cost for your friend after using your passes.
### Constraints
- $1 \le n,m \le 10^5$.
- $1 \le S, T, X, Y \le n$.
- $1 \le u, v \le n$.
- $1 \le w \le 10^9$.
### Example
Input:
```
6 6
1 6
1 4
1 2 5
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
```
Output:
```
2
```
