Bạn được cho một đồ thị với ~n~ đỉnh (được đánh số từ ~1~ đến ~n~) và ~m~ cạnh có hướng và có trọng số. Tìm đường đi có ~k~ cạnh với tổng trọng số nhỏ nhất. Một đường đi có thể đi qua một đỉnh hay cạnh nhiều lần.

Nếu không tồn tại đường đi nào có ~k~ cạnh, in ra IMPOSSIBLE.

Input

Dòng đầu tiên gồm ~3~ số nguyên dương ~n~, ~m~ và ~k~ ~(1 \le n \le 100, 0 \le m \le n \cdot (n-1), 1 \le k \le 10^9)~

~m~ dòng tiếp theo miêu tả các cạnh. Trong đó dòng thứ ~i~ gồm 3 số ~a_i~, ~b_i~ và ~c_i~ ~(1 \le a_i,b_i \le n, a_i \neq b_i, -10^9 \le c_i \le 10^9)~, miêu tả một cạnh có hướng nối từ ~a_i~ đến ~b_i~ với trọng số ~c_i~. Đồ thị trong input đảm bảo không có cạnh trùng hoặc cạnh nối cùng một đỉnh với nhau.

Output

In ra đường đi đi qua ~k~ cạnh với tổng trọng số nhỏ nhất. Nếu không tồn tại đường đi nào đi qua ~k~ cạnh thì in ra IMPOSSIBLE.

Sample 1

Input

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

Output

7

Sample 2

Input

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

Output

17

Sample 3

Input

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

Output

-156

Sample 4

Input

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

Output

IMPOSSIBLE

Note

Hình vẽ dưới đây cho thấy đồ thị trong hai sample đầu tiên. Đường đi tối ưu lần lượt là ~1 \rightarrow 2 \rightarrow 3~ và ~2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3~