NEWROAD

In a country, there are ~N~ cities and ~M~ roads connecting some of these cities. It is assumed that the roads are directed, and the road from city u to city v has a (non-negative) length of ~L(u,\;v)~.

A new road is to be constructed, and a list ~K~ of pairs of cities has been proposed that this road could connect. Each proposed road from city ~u~ to city ~v~ is accompanied by its respective length ~L(u,\;v)~.

Let's consider two given cities, ~s~ and ~t~. The task is to choose the proposed road that achieves the maximum reduction in distance from city ~s~ to city ~t~.

Input

The first line of input contains five natural numbers separated in pairs by a single space: ~N~, the number of cities; ~M~, the number of roads; ~K~, the number of proposed roads; ~s~, the starting city; and ~t~, the destination city. Each of the next ~M~ lines describes a road and contains three natural numbers ~u~, ~v~, ~L~ separated in pairs by a space: the starting city ~u~, the ending city ~v~, and its length ~L~. Each of the next ~K~ lines describes a proposed road and contains three natural numbers ~u~, ~v~, ~L~ separated in pairs by a space, as before.

The cities, roads, and proposed roads are numbered in ascending order starting from ~1~.

Output

The output should consist of a single line containing exactly one integer: the minimum distance from city ~s~ to city ~t~ achieved when selecting the best proposed road.

Note that it is possible that none of the proposed roads will reduce the distance from city ~s~ to city ~t~. In this case, none of the proposed roads should be selected, and the result should be the distance between ~s~ and ~t~, as in the existing road network.

Constraints

~2 \le N \le 10.000~, ~1 \le M \le 100.000~, ~1 \le K \le 10.000~
Every route that does not contain a cycle has a length at most ~2.000.000.000~
Execution time limit: 1 sec.
Maximum available memory: 128 MB.

Example of Input - Output

STDIN (newroad.in)

4 4 2 2 4
1 3 10
2 1 7
4 2 9
3 4 8
2 3 15
1 4 12

STDOUT (newroad.out)

19