有许多众所周知的算法可以找到从一个地点到另一个地点的最短路径。人们在汽车和手机上使用 GPS 设备，以显示到达目的地的最快方式。然而，在度假时，Troy 喜欢慢节奏旅行。他希望走一条通往目的地的最长路径，以便沿途参观许多新奇有趣的地方。

因此，一条有效的路径由一系列不同的城市 $c_1, c_2, \dots, c_k$ 组成，使得对于每个 $1 \le i < k$，都有一条从 $c_i$ 到 $c_{i+1}$ 的道路。

他不想访问任何城市超过一次。你能帮他找到最长的路径吗？

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，分别表示城市总数和连接这些城市的道路数量（$2 \le n \le 18$；$1 \le m \le n^2 - n$）。任意两个城市之间最多只有一条道路。城市编号从 $0$ 到 $n - 1$，其中 $0$ 是 Troy 的出发城市，$n - 1$ 是他的目的地。

接下来的 $m$ 行，每行包含三个整数 $s, d, l$。每个三元组表示有一条从城市 $s$ 到城市 $d$ 的单向道路，长度为 $l$ 公里（$0 \le s \le n - 1$；$0 \le d \le n - 1$；$s \neq d$；$1 \le l \le 10000$）。每条道路都是单向的：只能从 $s$ 到 $d$，不能反向行驶。保证至少存在一条从城市 $0$ 到城市 $n - 1$ 的路径。

对于至少 30% 的测试数据，满足 $n \le 8$。

输出格式

输出一个整数，表示从城市 $0$ 出发，以城市 $n - 1$ 结束，且不访问任何城市超过一次的最长路径长度。路径长度为沿途所经过道路的长度之和。

样例

输入 1

3 3
0 2 5
0 1 4
1 2 3

输出 1

7

说明 1

最短路径是直接从 $0$ 到 $2$，长度为 $5$ 公里。而从 $0$ 到 $1$ 再到 $2$ 的路径长度为 $4 + 3 = 7$ 公里，这条路径更长。