F. Farmer John's Cities
time limit per test
1 second
memory limit per test
250 megabytes
input
standard input
output
standard output

In the country of Farmer John, there exist $$$N$$$ cities and $$$M$$$ roads connecting some of these cities. We assume that the roads are directional and that the road going from city $$$u$$$ to city $$$v$$$ has a non-negative length $$$L(u,v)$$$.

A new road is to be built, and therefore, you are given a list of $$$K$$$ pairs of cities that this road could connect. Each proposed road from city $$$u$$$ to city $$$v$$$ is accompanied by its corresponding length $$$L(u,v)$$$.

You are also given two cities, $$$s$$$ and $$$t$$$. Your goal is to choose at most one of the proposed roads to achieve the minimum distance from city $$$s$$$ to city $$$t$$$ and print that distance.

Input

The first line contains five positive integers, $$$N$$$ $$$(1 \leq N \leq 10^4)$$$, $$$M$$$ $$$(1 \leq M \leq 10^5)$$$, $$$K$$$ $$$(1 \leq K \leq 10^4)$$$, $$$s$$$, and $$$t$$$ $$$(1 \leq s,t \leq N)$$$ respectively. Each of the following $$$M$$$ $$$(1\leq M \leq 10^5)$$$ lines describes a road and contains three integers, $$$u$$$, $$$v$$$, $$$(1 \leq u,v \leq N)$$$ and $$$L$$$ $$$(1 \leq L \leq 10^6)$$$ respectively. A directed road from city $$$u$$$ to city $$$v$$$, and the length of that road. The following $$$K$$$ lines describe the proposed roads, each containing again three integers, the start of the road, the end of the road, and its length respectively.

Output

You must print a single non-negative integer, the minimum distance possible after building one of the $$$K$$$ proposed roads.

Example
Input
4 4 2 2 4
1 3 10
2 1 7
4 2 9
3 4 8
2 3 15
1 4 12
Output
19
Note

If none of the proposed roads achieve a smaller distance, then you should just print the smallest distance in the already existing network.