406978: GYM102644 F Min Path

You are given a graph with $$$n$$$ vertices (numbered $$$1$$$ through $$$n$$$) and $$$m$$$ directed weighted edges. Find the minimum possible total weight of a path with $$$k$$$ edges. A path can visit the same vertex or edge multiple times.

If there is no path with $$$k$$$ edges, print IMPOSSIBLE instead.

The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \leq n \leq 100$$$, $$$0 \leq m \leq n \cdot (n - 1)$$$, $$$1 \leq k \leq 10^9$$$) — the number of vertices, the number of edges and the length of a path.

The following $$$m$$$ lines describe edges. The $$$i$$$-th of these lines contains three integers $$$a_i$$$, $$$b_i$$$ and $$$c_i$$$ ($$$1 \leq a_i, b_i \leq n, a_i \neq b_i$$$, $$$-10^9 \leq c_i \leq 10^9$$$), denoting a directed edge from $$$a_i$$$ to $$$b_i$$$ of weight $$$c_i$$$. There are no self-loops or multiple edges.

Print the minimum possible sum of weights of a path with $$$k$$$ edges, or the word IMPOSSIBLE if there is no such path.

3 4 2
1 2 12
2 3 -5
3 1 20
2 1 -1

7

3 4 5
1 2 12
2 3 -5
3 1 20
2 1 -1

17

6 5 3
1 3 -50
2 4 -51
4 3 -52
3 6 -53
4 5 -54

-156

6 5 4
1 3 -50
2 4 -51
4 3 -52
3 6 -53
4 5 -54

IMPOSSIBLE

The drawing below shows the graph in two first sample tests. The optimal paths are respectively $$$1 \rightarrow 2 \rightarrow 3$$$ and $$$2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3$$$.