도로 재포장

바이트랜드의 도로 대부분은 상태가 매우 나쁘다. 바이트랜드의 왕은 백성들의 수많은 요청을 받아들여 일부 도로를 재포장하기로 했다. 바이트랜드에는 $1$번부터 $n$번까지 번호가 매겨진 $n$개의 도시가 있다. 일부 도시 쌍은 단방향 도로로 연결되어 있다. 수석 건축가는 재포장하기에 적합하다고 판단한 도로 $m$개를 골랐고, 각 도로마다 보수 비용을 산정했다.

왕은 모든 백성이 도로 개선을 직접 체감하기를 바란다. 어떤 도시의 주민이 만족하려면, 재포장된 도로를 이용해 그 도시로 들어올 수 있고 동시에 그 도시에서 나갈 수도 있어야 한다. 전체 보수 비용이 최소가 되도록 재포장 계획을 세워야 한다.

정리하면, 주어진 도로 중 일부를 골라 모든 도시가 그 도시에서 나가는 선택된 도로를 적어도 하나 갖고, 그 도시로 들어오는 선택된 도로도 적어도 하나 갖도록 하되, 선택한 도로들의 비용 합을 최소로 하라.

첫째 줄에 두 정수 $n$과 $m$이 주어진다 ($2 \le n \le 300$, $1 \le m \le n^2$). 각각 도시의 수와 재포장 대상 단방향 도로의 수이다. 이어지는 $m$개의 줄에는 각각 세 정수 $x$, $y$, $k$가 주어진다 ($1 \le x, y \le n$, $0 \le k \le 10^5$). 이는 도시 $x$에서 도시 $y$로 가는 도로를 재포장하는 비용이 $k$임을 뜻한다. 순서쌍 $(x, y)$는 입력에 최대 한 번 등장한다. 시작 도시와 도착 도시가 같은 도로(자기 자신으로 가는 도로)가 있을 수도 있다.

왕의 요구 조건을 만족하는 재포장 계획의 최소 비용을 정수 하나로 출력한다. 그러한 계획이 존재하지 않으면 대신 NIE를 출력한다.