Problem Description

There are $N$ cities numbered from $1$ to $N$. Initially, there are no roads between these cities.

There are $M$ road construction proposals. The $i$-th proposal is to build a one-way road from city $s_i$ to city $t_i$ ($s_i < t_i$) for a cost of $c_i$ yen.

We want to adopt some of these proposals such that city $w$ is reachable from city $x$ and city $y$ is reachable from city $z$.

Find the minimum cost required to satisfy the above conditions.

Input Format

The input is given from the standard input in the following format:

$N$ $M$ $w$ $x$ $y$ $z$ $c_1$ $s_1$ $t_1$ $\vdots$ $c_M$ $s_M$ $t_M$

Output Format

Output the minimum cost to make city $w$ reachable from city $x$ and city $y$ reachable from city $z$. If such a selection of proposals does not exist, output Impossible instead.

Sample Input and Output

Sample Input #1

5 6
2 5 1 4
1 3 5
3 2 5
1 1 2
1 3 4
4 1 4
3 2 3

Sample Output #1

6

Sample Input #2

5 5
1 3 2 5
4 2 3
2 2 4
5 3 5
1 1 4
3 4 5

Sample Output #2

Impossible

Sample Input #3

5 8
1 3 2 5
42 2 3
32 2 4
12 3 5
94 1 4
21 4 5
79 1 2
22 1 5
90 1 3

Sample Output #3

133

Notes/Hints

Constraints

• All input values are integers.
• $4 \leq N \leq 10^5$
• $2 \leq M \leq 2 \times 10^5$
• $1 \leq w < x \leq N$
• $1 \leq y < z \leq N$
• $1 \leq c_i \leq 10^9$
• $1 \leq s_i < t_i \leq N$
• $w, x, y, z$ are pairwise distinct.
• $(s_i, t_i) \ne (s_j, t_j)$ for $i \ne j$

Sample Explanation 1

• By adopting proposals $1, 3, 4, 6$, the total cost is $6$ yen, which is the minimum.

Sample Explanation 2

• No matter how proposals are chosen, it is impossible to make the specified cities reachable.

见题面 Input 部分

见题面 Output 部分