406978: GYM102644 F Min Path

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Min Pathtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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

ExamplesInput
3 4 2
1 2 12
2 3 -5
3 1 20
2 1 -1
Output
7
Input
3 4 5
1 2 12
2 3 -5
3 1 20
2 1 -1
Output
17
Input
6 5 3
1 3 -50
2 4 -51
4 3 -52
3 6 -53
4 5 -54
Output
-156
Input
6 5 4
1 3 -50
2 4 -51
4 3 -52
3 6 -53
4 5 -54
Output
IMPOSSIBLE
Note

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$$$.

加入题单

上一题 下一题 算法标签: