Road Renovation

Most of the roads in Byteland are in terrible condition. Responding to numerous requests from his subjects, the King of Byteland has decided to renovate some of the roads. Byteland has $n$ cities numbered from $1$ to $n$. Some ordered pairs of cities are joined by one-way roads. The chief builder picked $m$ roads that he considers worth renovating and estimated a repair cost for each one.

The King wants every citizen to feel the improvement firsthand. He decided that the residents of a city are satisfied only if, using renovated roads, one can both enter that city and leave that city. Plan the renovations so that their total cost is as small as possible.

In other words, choose a subset of the given roads so that every city has at least one chosen road leaving it and at least one chosen road entering it, and the total cost of the chosen roads is minimized.

The first line contains two integers $n$ and $m$ ($2 \le n \le 300$, $1 \le m \le n^2$): the number of cities and the number of one-way roads available for renovation. Each of the next $m$ lines contains three integers $x$, $y$, and $k$ ($1 \le x, y \le n$, $0 \le k \le 10^5$), meaning that renovating the road from city $x$ to city $y$ costs $k$. Each ordered pair $(x, y)$ appears at most once in the input. A road may start and end at the same city.

Print a single integer: the minimum possible total cost of a renovation plan that meets the King's requirement. If no such plan exists, print NIE instead.