{"raw_statement":[{"iden":"statement","content":"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.\n\nIf there is no path with $k$ edges, print _IMPOSSIBLE_ instead.\n\nThe first line contains three integers $n$, $m$ and $k$ ($1 <= n <= 100$, $0 <= m <= n dot.op (n -1)$, $1 <= k <= 10^9$) — the number of vertices, the number of edges and the length of a path.\n\nThe following $m$ lines describe edges. The $i$-th of these lines contains three integers $a_i$, $b_i$ and $c_i$ ($1 <= a_i, b_i <= n, a_i eq.not b_i$, $-10^9 <= c_i <= 10^9$), denoting a directed edge from $a_i$ to $b_i$ of weight $c_i$. There are no self-loops or multiple edges.\n\nPrint the minimum possible sum of weights of a path with $k$ edges, or the word _IMPOSSIBLE_ if there is no such path.\n\nThe drawing below shows the graph in two first sample tests. The optimal paths are respectively $1 arrow.r 2 arrow.r 3$ and $2 arrow.r 1 arrow.r 2 arrow.r 1 arrow.r 2 arrow.r 3$.\n\n"},{"iden":"input","content":"The first line contains three integers $n$, $m$ and $k$ ($1 <= n <= 100$, $0 <= m <= n dot.op (n -1)$, $1 <= k <= 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 <= a_i, b_i <= n, a_i eq.not b_i$, $-10^9 <= c_i <= 10^9$), denoting a directed edge from $a_i$ to $b_i$ of weight $c_i$. There are no self-loops or multiple edges."},{"iden":"output","content":"Print the minimum possible sum of weights of a path with $k$ edges, or the word _IMPOSSIBLE_ if there is no such path."},{"iden":"examples","content":"Input3 4 2\n1 2 12\n2 3 -5\n3 1 20\n2 1 -1\nOutput7\nInput3 4 5\n1 2 12\n2 3 -5\n3 1 20\n2 1 -1\nOutput17\nInput6 5 3\n1 3 -50\n2 4 -51\n4 3 -52\n3 6 -53\n4 5 -54\nOutput-156\nInput6 5 4\n1 3 -50\n2 4 -51\n4 3 -52\n3 6 -53\n4 5 -54\nOutputIMPOSSIBLE\n"},{"iden":"note","content":"The drawing below shows the graph in two first sample tests. The optimal paths are respectively $1 arrow.r 2 arrow.r 3$ and $2 arrow.r 1 arrow.r 2 arrow.r 1 arrow.r 2 arrow.r 3$.  "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be a directed weighted graph with:  \n- $ V = \\{1, 2, \\dots, n\\} $: set of vertices,  \n- $ E \\subseteq V \\times V $: set of directed edges,  \n- $ w: E \\to \\mathbb{Z} $: weight function, where $ w(a_i, b_i) = c_i $ for each edge $ (a_i, b_i, c_i) \\in E $.  \n\nLet $ k \\in \\mathbb{Z}^+ $ be the fixed number of edges in the desired path.\n\n**Constraints**  \n1. $ 1 \\le n \\le 100 $  \n2. $ 0 \\le m \\le n(n-1) $  \n3. $ 1 \\le k \\le 10^9 $  \n4. For each edge $ (a_i, b_i, c_i) $: $ a_i \\ne b_i $, $ -10^9 \\le c_i \\le 10^9 $  \n5. No self-loops or multiple edges.  \n\n**Objective**  \nCompute:  \n$$\n\\min \\left\\{ \\sum_{j=1}^{k} w(e_j) \\,\\middle|\\, \\text{there exists a path } v_0 \\to v_1 \\to \\cdots \\to v_k \\text{ with } (v_{j-1}, v_j) \\in E \\text{ for all } j \\in \\{1, \\dots, k\\} \\right\\}\n$$  \nIf no such path exists, output **IMPOSSIBLE**.","simple_statement":"Given a directed weighted graph with n vertices and m edges, find the minimum total weight of any path that uses exactly k edges. You can reuse vertices and edges. If no such path exists, print \"IMPOSSIBLE\".","has_page_source":false}