28131번 - K-지폐

지수가 사는 나라는 $1$번부터 $N$번 도시까지 총 $N$개의 도시와 도로 $M$개가 존재한다. $i$번 도로는 $u_{i}$번 도시에서 $v_{i}$번 도시로 갈 수 있는 단방향 도로이며, 이용 시 $w_{i}$만큼의 이용료를 지불해야 한다.

지수는 $S$번 도시에서 $T$번 도시로 여행을 가려고 한다. 지수는 $T$번 도시에 도착하는 순간 지금까지 이용한 도로의 이용료를 합하여 지불한다.

지수는 $K$원 지폐를 너무 좋아한 나머지, 지갑 안에 무한히 많은 $K$원 지폐를 넣고 다닌다. 지수는 지갑 안에 $K$원 지폐를 제외한 어떤 단위의 지폐도 가지고 다니고 싶어 하지 않기 때문에 이용료 합을 지불한 뒤 받는 거스름돈이 없도록 여행을 떠나고 싶다. 다시 말해 지수는 이용료 합이 $K$의 배수가 되도록 여행하고 싶다.

지수가 거스름돈을 받지 않으면서 $T$번 도시까지 여행하는데 지불해야 하는 이용료 합의 최솟값을 구하자.

첫째 줄에 $N$, $M$, $K$가 주어진다. $(2\leq N\leq 10\,000; 1\leq M\leq \min\left(100\,000, N(N-1)\right); 1\leq K\leq 50)$

둘째 줄에 $S$와 $T$가 공백으로 구분되어 주어진다. $(1\leq S,T\leq N;S\neq T)$

셋째 줄부터 $M$개의 줄에 걸쳐 $u\ v\ w$가 공백으로 구분되어 주어진다. $u$번 도시에서 $v$번 도시로 가는 도로의 이용료가 $w$원이라는 뜻이다. $(1 \leq u,v \leq N; u\neq v; 1\leq w \leq 1\,000)$

입력으로 주어지는 모든 값은 정수다.

문제의 조건을 만족하도록 여행할 때, 지수가 지불해야하는 이용료 합의 최솟값을 출력한다.

조건을 만족하면서 여행할 수 없다면 IMPOSSIBLE을 출력한다.