Problem Description

E869120 is a salesman and must return to the shop after visiting all buildings exactly once.

The city where E869120 lives has $N$ buildings and $M$ roads. The buildings are numbered 1-indexed, with the shop being building $1$.

Road $i$ connects building $s_i$ and building $t_i$ with a distance of $d_i$.

However, for security reasons, the roads close after a certain amount of time has passed.

Road $i$ closes after $time_i$ time units have passed since E869120's departure.

Therefore, when using that road, it must be traversed within $time_i$ time units.

E869120 wondered:

"How many ways are there to return in the shortest time?"

You, being an excellent programmer, have been asked to create a program to solve this.

Find the shortest path and the total number of ways to return in the shortest time. Note that E869120 moves a distance of 1 per time unit, and roads can be traversed in both directions.

Input Format

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

$ N $ $ M $ $ s_1 $ $ t_1 $ $ d_1 $ $ time_1 $ $ s_2 $ $ t_2 $ $ d_2 $ $ time_2 $ ... $ s_M $ $ t_M $ $ d_M $ $ time_M $

• The first line contains the integers $ N $ and $ M $.
• The next $ M $ lines contain the integers $ s_i $, $ t_i $, $ d_i $, and $ time_i $ separated by spaces.

Output Format

Output the shortest path and the total number of ways to return in the shortest time, separated by a space.

If such a path does not exist, output "IMPOSSIBLE".

Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

3 3
1 2 1 6
2 3 2 6
3 1 3 6

Sample Output #1

6 2

Sample Input #2

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

Sample Output #2

3 1

Sample Input #3

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

Sample Output #3

IMPOSSIBLE

Sample Input #4

3 2
1 2 3 20
2 3 2 20

Sample Output #4

IMPOSSIBLE

Notes/Hints

Constraints

• $1 \leq N \leq 16$
• $1 \leq s_i < t_i \leq N$ (not necessarily in the input example)
• $1 \leq d_i \leq 1,000,000,000,000$
• $1 \leq time_i \leq 1,000,000,000,000$
• For any $ i, j $, $(s_i, t_i) \neq (s_j, t_j)$

Partial Points

• 15 points are awarded for correctly solving all datasets where $2 \leq N \leq 8$.
• 85 points are awarded for correctly solving the remaining datasets.

Sample Explanation 1

Going $ 1 -> 2 -> 3 -> 1 $ or $ 1 -> 3 -> 2 -> 1 $ takes 6 time units, which is the shortest path.

Sample Explanation 2

Road 1 closes after 1 time unit, so $ 1 -> 3 -> 2 -> 1 $ is not possible.

Sample Explanation 3

Neither $ 1 -> 2 -> 3 -> 1 $ nor $ 1 -> 3 -> 2 -> 1 $ is possible, so E869120 cannot fulfill their duty.

见题面 Input 部分

见题面 Output 部分