You are given a graph containing \(n\) vertices and \(m\) directed arcs. Vertices are numbered from \(1\) to \(n\), inclusive; and
arcs are numbered from \(1\) to \(m\), inclusive. The \(i\)-th arc starts from the \(s_i\)-th vertex, ends at the \(t_i\)-th vertex and has a
cost of \(c_i\).

In this problem, a valid path is a sequence of arcs in which the first one starts at the \(1\)-st vertex, the last one ends at
the \(n\)-th vertex and every arc ends at the starting vertex of the next one. More formally, a valid path can be represented
by a sequence of indices \((e_1,e_2,...,e_k)\) satisfying all below conditions:

• \(1 \le e_1, e_2, ..., e_k \le m\)
• \(s_{e_1} = 1\)
• \(s_{e_k} = n\)
• \(t_{e_j} = s_{e_j}+1\) for all j such that \(0 < j < k\)

Please note that these indices do not need to be distinct, meaning that a valid path may walk through some edge
multiple times.

Your task is to mark some (possibly none or all) arcs of the given graph special so as to fullfill this requirements:

Every valid path of this graph passes through special arcs exactly once. In other words, if the sequence of indices
\((f_1,f_2,...,f_k)\) represents a valid path, there should be exactly one index \(l\) such that \(1 \le l \le k\) and the \(f_l\)-th arc is
marked special. Moreover, the total cost of special arcs should be as small as possible.

Input

The input contains multiple test cases. Each test case is presented as below:

• The first line contains two integers \(n\) and \(m (2 \le n \le 100, 1 \le m \le 2500)\) denoting the number of vertices
  and arcs of the graph, respectively.
• In the next \(m\) lines, each contains three integers \(s_i , t_i\) and \(c_i (1 \le s_i , t_i \le n, 1 \le c_i \le 10^9 )\) denoting the starting
  and ending vertices of the i-th arc and its cost, respectively.

• The last line is a blank line.
  The input is terminated by two zeros which do not represent a test case. It is guaranteed that:

  • For every arc, its starting vertex differs from its ending one.

  • For every graph, each ordered pair \((s_i , t_i)\) appears at most once.

  • A valid path always exists.

The sum of n over all test cases does not exist 1000. The sum of m over all test cases does not exist 25000.

Output

• Write the result of each test case in a single line: If it is impossible to mark arcs in order to satisfy the above require-
  ments, print “IMPOSSIBLE” (without quotes). Otherwise, print the minimum possible total cost of special arcs.

Example

4 5
1 2 1
2 3 1
3 4 1
1 3 8
2 4 8
2 2
2 1 1
1 2 1
0 0

9
IMPOSSIBLE