H. Zürich Trams
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

It is a very rare sight when public transportation systems are as well designed as they are in Zürich. Residents of Zürich often take this for granted, as they reach any destination in time by following a path that is built for them in a transportation app.

In this problem, we are going to make you appreciate it. To make it simpler, we will assume that Zürich only has trams as its public transport, and we will model the connections between the stations of the Zürich tram network as a tree, meaning that the tram network, which consists of $$$n$$$ stations numbered $$$1$$$ through $$$n$$$, is connected and has no loops.

In total, there are $$$m$$$ trams; the $$$i$$$-th tram can be represented by three integers $$$s_i$$$, $$$e_i$$$, and $$$k_i$$$: the starting location of the tram, the ending location of the tram, and the pace of the tram, respectively. In the morning, the $$$i$$$-th tram starts at the location $$$s_i$$$ and travels to the location $$$e_i$$$; after reaching $$$e_i$$$, it travels back to $$$s_i$$$. This process repeats indefinitely; the tram always takes the shortest path, and it takes the time $$$k_i$$$ to travel a direct connection between two stations.

Bjarki lives at the station $$$a$$$ and has been working until the early morning. He just realized that his favorite rave has already started. He quickly put his clothes on, opened his travel app, and put in his destination, which is located at the station $$$b$$$. When a tram enters the station that Bjarki is located in, he can enter it; this takes a negligible amount of time. Then he can leave the tram at any station, which also takes a negligible amount of time.

Help Bjarki get to the rave as quickly as possible!

Input

The first line contains four integers $$$n$$$, $$$m$$$, $$$a$$$, and $$$b$$$ ($$$2 \leq n \leq 1\;000$$$; $$$1 \leq m \leq 1\;000$$$; $$$1 \leq a,b \leq n$$$): the number of stations in the Zürich tram network, the number of trams, and Bjarki's home station and his favorite rave's station, respectively. It is guaranteed that $$$a$$$ and $$$b$$$ are distinct.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$, $$$v$$$ ($$$1 \leq u,v \leq n$$$), indicating a direct connection between the stations $$$u$$$ and $$$v$$$ in the tram network. It is guaranteed that it is possible to reach any station from any other station via a sequence of direct connections.

The $$$i$$$-th of the following $$$m$$$ lines contains three integers $$$s_i$$$, $$$e_i$$$, $$$k_i$$$ ($$$1 \leq s_i, e_i \leq n$$$; $$$1 \leq k_i \leq 10^5$$$), representing the starting station, ending station, and the pace of the $$$i$$$-th tram.

It is guaranteed that $$$s_i$$$ and $$$e_i$$$ are distinct. It is possible that a connection is used by more than one tram, and some of the connections might not be used by any tram, meaning that Bjarki can't use them.

Assume that all trams simultaneously start moving from their starting stations the moment Bjarki reaches the station near his home.

Output

Output a single integer, the minimum amount of time it takes for Bjarki to travel to the rave. If there is no possible way for Bjarki to travel to the rave via the tram network, output $$$-1$$$.

Examples
Input
3 2 1 3
1 2
2 3
2 1 5
2 3 3
Output
15
Input
2 1 2 1
1 2
2 1 10
Output
10