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 <= 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.
Print the minimum possible sum of weights of a path with $k$ edges, or the word _IMPOSSIBLE_ if there is no such path.
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$.
## Input
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.
## Output
Print the minimum possible sum of weights of a path with $k$ edges, or the word _IMPOSSIBLE_ if there is no such path.
[samples]
## Note
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$.
**Definitions**
Let $ G = (V, E) $ be a directed weighted graph with:
- $ V = \{1, 2, \dots, n\} $: set of vertices,
- $ E \subseteq V \times V $: set of directed edges,
- $ 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 $.
Let $ k \in \mathbb{Z}^+ $ be the fixed number of edges in the desired path.
**Constraints**
1. $ 1 \le n \le 100 $
2. $ 0 \le m \le n(n-1) $
3. $ 1 \le k \le 10^9 $
4. For each edge $ (a_i, b_i, c_i) $: $ a_i \ne b_i $, $ -10^9 \le c_i \le 10^9 $
5. No self-loops or multiple edges.
**Objective**
Compute:
$$
\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\}
$$
If no such path exists, output **IMPOSSIBLE**.