Most roads in Byteland are in a deplorable state. The King of Byteland, yielding to the numerous requests of his subjects, has decided to renovate some of the roads. There are $n$ cities in Byteland, numbered from 1 to $n$. Some pairs of cities are connected by one-way roads. The chief builder of Byteland has selected $m$ roads that he believes are suitable for renovation. For each of these roads, he has estimated the cost of its repair.

The King wants every citizen of Byteland to personally feel the improvement in road quality. He has assumed that the residents of any city will be satisfied if it is possible to enter their city and leave their city using at least one renovated road. The repairs must be planned so that their total cost is as low as possible. Creating a road renovation plan that meets the King's requirements has fallen to you.

Input

The first line of the input contains two integers $n$ and $m$ ($2 \le n \le 300$, $1 \le m \le n^{2}$) specifying the number of cities in Byteland and the number of one-way roads suitable for renovation. The next $m$ lines of the input contain three integers $x$, $y$, and $k$ ($1 \le x, y \le n$, $0 \le k \le 10^{5}$), meaning that renovating the road leading from city $x$ to city $y$ costs $k$ bytalars. Each ordered pair $x, y$ will appear in the input at most once. Note that there may be a road starting and ending in the same city.

Output

The first and only line of the output should contain a single integer specifying the minimum possible cost of carrying out the renovation according to the King's requirements, or the word NIE if it is not possible to prepare a plan that meets the King's requirements.

Examples

Input 1

4 6
1 2 1
2 1 2
1 3 3
3 1 4
3 2 5
4 4 6

Output 1

16

Input 2

4 4
1 2 5
2 3 4
3 1 8
2 4 7

Output 2

NIE