大多数 Bajtocja 的道路都处于极其糟糕的状态。Bajtocja 的国王在听取了大量臣民的请求后，决定对部分道路进行修缮。在 Bajtocja 有 $n$ 个城市，编号从 1 到 $n$。部分城市之间通过单向道路连接。Bajtocja 的首席建筑师挑选了 $m$ 条他认为适合翻修的道路。对于每一条道路，他都预估了其修复费用。

国王希望每一位 Bajtocja 的公民都能亲身感受到道路质量的提升。他设想，只要任意城市的居民都能够至少通过一条翻修后的道路进入该城市，也能通过至少一条翻修后的道路离开该城市，他们就会感到满意。修缮方案应使总费用尽可能小。制定一份满足国王要求的道路翻修计划，这一任务就交给了你。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ （$2 \le n \le 300$，$1 \le m \le n^{2}$），分别表示 Bajtocja 中的城市数以及可翻修的单向道路数。接下来的 $m$ 行中，每行有三个整数 $x$、$y$ 和 $k$ （$1 \le x, y \le n$，$0 \le k \le 10^{5}$），表示从城市 $x$ 到城市 $y$ 的道路修缮费用为 $k$ bajtalar。每组有序对 $x, y$ 在输入中最多出现一次。注意，可能存在起点和终点为同一个城市的道路。

输出格式

输出仅一行，包含一个整数，表示满足国王要求的最小翻修费用；如果不存在满足条件的方案，则输出 NIE。

示例

输入

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

输出

16

输入 2

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

输出 2

NIE