{"code":"icpc21graph","name":"Graph","description":"You are given a graph containing $n$ vertices and $m$ directed arcs. Vertices are numbered from $1$ to $n$, inclusive; and\r\narcs 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\r\ncost of $c_i$.\r\n\r\nIn 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\r\nthe $n$-th vertex and every arc ends at the starting vertex of the next one. More formally, a valid path can be represented\r\nby a sequence of indices $(e_1,e_2,...,e_k)$ satisfying all below conditions:\r\n\r\n- $1 \\le e_1, e_2, ..., e_k \\le m$\r\n- $s_{e_1} = 1$\r\n- $s_{e_k} = n$\r\n- $t_{e_j} = s_{e_j}+1$ for all j such that $0 < j < k$\r\n\r\nPlease note that these indices do not need to be distinct, meaning that a valid path may walk through some edge\r\nmultiple times.\r\n\r\nYour task is to mark some (possibly none or all) arcs of the given graph special so as to fullfill this requirements:\r\n\r\nEvery valid path of this graph passes through special arcs exactly once. In other words, if the sequence of indices\r\n$(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\r\nmarked special. Moreover, the total cost of special arcs should be as small as possible.\r\n\r\n

Input

\r\n\r\nThe input contains multiple test cases. Each test case is presented as below:\r\n- The first line contains two integers $n$ and $m (2 \\le n \\le 100, 1 \\le m \\le 2500)$ denoting the number of vertices\r\nand arcs of the graph, respectively.\r\n- In the next $m$ lines, each contains three integers $s_i\r\n, t_i$ and $c_i (1 \\le s_i\r\n, t_i \\le n, 1 \\le c_i \\le 10^9\r\n)$ denoting the starting\r\nand ending vertices of the i-th arc and its cost, respectively.\r\n- The last line is a blank line.\r\nThe input is terminated by two zeros which do not represent a test case. It is guaranteed that:\r\n - For every arc, its starting vertex differs from its ending one.\r\n - For every graph, each ordered pair $(s_i\r\n , t_i)$ appears at most once.\r\n\r\n - A valid path always exists.\r\n\r\nThe sum of n over all test cases does not exist 1000. The sum of m over all test cases does not exist 25000.\r\n\r\n

Output

\r\n\r\n- 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-\r\nments, print “IMPOSSIBLE” (without quotes). Otherwise, print the minimum possible total cost of special arcs.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 4 5\r\n 1 2 1\r\n 2 3 1\r\n 3 4 1\r\n 1 3 8\r\n 2 4 8\r\n 2 2\r\n 2 1 1\r\n 1 2 1\r\n 0 0\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 9\r\n IMPOSSIBLE\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n In the first test case, there are three valid paths, whose arc indices are (4, 3), (1, 5) and (1, 2, 3). The optimal solution\r\n is to mark the first and the forth arcs special. Note that marking the first and the third arcs is not a valid way, since the\r\n valid path (1, 2, 3) will pass through special arcs twice.\r\n\r\n In the second test case, please be aware that a valid path can contain duplicated arcs. Hence, (2, 1, 2) or even\r\n (2, 1, 2, 1, 2) are valid paths of this graph. Consequently, marking the second arc is not possible, as it appears more\r\n than once in those valid paths. As a result, solution does not exist.","points":400.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}