题目描述

本题译自 CCO 2015 Day1 T2「Artskjid」

你可以通过许多的算法找到从一个地方到另外一个地方的最短路径。人们在他们的车上安装 GPS 设备然后他们的手机告诉他们最快的到达目的地的方式。然而，当在假期时，Troy 喜欢慢慢旅游。他想找最长的到目的地的路径以便他可以在路途中看许多新的以及有趣的地方。

因此，一个有效的路径包含一个不同城市的序列 $c_1,c_2,...,c_k$，并且对于每个 $1\le i<k$，有道路从 $c_i$ 通往 $c_{i+1}$。

他不想重复访问任何城市，请帮他找出最长路径。

输入格式

第一行输入包括两个整数 $n,m$，分别表示城市总数和连接城市间的道路数，两城市间至多有一条道路。城市编号从 $0$ 到 $n-1$，Troy 一开始在城市 $0$，城市 $n-1$ 是他的目的地。

接下来 $m$ 行每行三个整数 $s,d,l$，每个三元组表示这里有一条长为 $l$ 的从城市 $s$ 到城市 $d$ 的路。每条路都是有向的，只能从 $s$ 到 $d$，不能反向。保证有一条从城市 $0$ 到 $n-1$ 的路径。

输出格式

输出一个整数表示以城市 $0$ 为起点，以 $n-1$ 为终点的最长路径长度，并且其中不重复访问城市，路径长度是所经过的道路长度之和。

3 3
0 2 5
0 1 4
1 2 3

7

数据范围与提示

对于至少 $30\%$ 的数据，$n\le 8$；
对于 $100\%$ 的数据，有 $2\le n \le 18,$ $1\le m \le n^2-n,$ $0\le s,d \le n-1,$ $s\neq d,$ $1\le l\le 10000$。