Problem D
Fend Off Titan

You are a righteous knight in a kingdom with $N$ villages with $M$ bidirectional roads. The villages are labeled from $1$ to $N$ while the roads are labeled from $1$ to $M$. The $i$-th road connects two different villages $A_ i$ and $B_ i$ with a length of $W_ i$. No two roads connect the same pair of villages.

You are requested by your King to deliver a message between two palaces located at village $X$ and village $Y$. You want to find the shortest path between the two villages, but unfortunately... There are evil shamans on your way! Worse, some of them also transformed themselves into titans! Specifically, for the $i$-th road:

• If $C_ i = 0$, then $i$-th road has no enemy.

• If $C_ i = 1$, then $i$-th road has a shaman.

• If $C_ i = 2$, then $i$-th road has a titan.

You are brave and powerful enough to slay the enemies (i.e. shamans and titans), but you just prefer to avoid them, especially the titans. So you want to find the best path from village $X$ to village $Y$ such that, ordered by your priority:

1. You want the total number of titans you encountered to be as few as possible.

2. You want the total number of shamans you encountered to be as few as possible.

3. You want the shortest path.

Can you help yourself by finding an algorithm to fend off titan?

Input

The first line contains four integers: $N~ (2 \le N \le 100)$, $M~ (0 \le M \le \frac{N \times (N-1)}{2})$, $X~ (1 \le X \le N)$, and $Y~ (1 \le Y \le N, X \neq Y)$.

The next $M$ lines contain the roads, each on one line. Each road is given in the form of four integers, $A_ i~ (1 \le A_ i \le N)$, $B_ i~ (1 \le B_ i \le N)$, $W_ i~ (1 \le W_ i \le 1~ 000~ 000~ 000)$, and $C_ i~ (0 \le C_ i \le 2)$.

Output

Print the total length, the total number of shamans, and the total number of titans in the best possible path. If you cannot go from village $X$ to village $Y$, print “IMPOSSIBLE” instead.

Subtasks

1. ($18$ Points): $M=N-1$, $A_ i = i$ and $B_ i = i+1$, $\forall i \in [1..M]$.

2. ($17$ Points): $M=N-1$ and all villages are connected.

3. ($7$ Points): $C_ i = 0$, $\forall i \in [1..M]$.

4. ($19$ Points): $C_ i = 1$, $\forall i \in [1..M]$.

5. ($27$ Points): $C_ i \leq 1$, $\forall i \in [1..M]$.

6. ($12$ Points): No additional constraint.

Explanation of Sample 1

There is only one possible path from village $4$ to village $1$. The path has length of $13$ and you have to encounter $0$ shamans and $2$ titans in total.

Explanation of Sample 2

There is actually a direct road from village $1$ to village $6$. However, the only titan in the whole kingdom is there, thus you should consider other paths. The shaman between village $2$ and village $3$ is avoidable, but the one between village $5$ and village $6$ is not. The shortest path for you to encounter just $1$ shaman is: $1-2-4-3-5-6$ with a total length of $24$.

Explanation of Sample 3

As village $3$ is isolated, it is impossible to reach it from village $1$.

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

13 0 2

6 8 1 6
1 6 5 2
1 2 10 0
2 3 2 1
3 4 4 0
4 2 6 0
3 5 1 0
4 5 9 0
5 6 3 1

24 1 0

3 1 1 3
1 2 1 0

IMPOSSIBLE