From Constanța 2 Timișoara

Adi of Adi and Sorin would like to visit their country this summer. They live in a country that can be represented as a graph with $N$ nodes and $M$ edges, where each city is a node and each bidirectional road between two cities is a weighted edge in the same graph (where the weight of the edge represents the length of the road in kilometers).

Since they really like the cities Constanța and Timișoara, they decided to visit both of these cities in their vacantion. More formaly, we will note the city of Constanța as node $X$ and the city of Timișoara as node $Y$. Now, if they want to start their journey in city $u$ and end it in city $v$, then their path will have the following properties:

• the length of the path is as small as possible (where the length is equal to the sum of weights of the edges in the path);
• the path visits both $X$ and $Y$.

Task

Let $d(u, v)$ be the length of the path that Adi of Adi and Sorin will visit if they start their journey in node $u$ and end it in node $v$. Note that a node or an edge can occur multiple times in the path. Your task is to calculate $\sum_{ 1 \leq u < v \leq N} d (u, v)$. Since this number can be very large, calculate it modulo $10^{9} + 9$.

Input data

The first line of the input contains the numbers $N$, $X$, $Y$ and $M$. The next $M$ lines will each contain three numbers $u$, $v$ and $c$, representing a weighted edge between $u$ and $v$ of weight $c$.

Output data

Output a single number, the sum of $d(u, v)$ for all ordered pairs of nodes modulo $10^{9} + 9$.

Constraints and clarifications

• $1 \leq N , M \leq 250 \ 000$
• $1 \leq X ,Y \leq N$
• $1 \leq u, v \leq N$
• $1 \leq c \leq 10^{9}$
• There will be no self-loops or multiple edges in the input.

Example

stdin

3 2 1 3
1 2 1
3 1 1
3 2 3

stdout

6

Explanation

$d(1, 2) + d(1, 3) + d(2, 3) = 1 + 3 + 2 = 6$