题目描述

给定一个$n$个点，$m$条边的有向图，要求找到一条路径，从$1$号点出发，以$n$号点为终点，并且不能重复经过某一个点，使得这个路径最长。

输入格式

第一行输入两个整数$n,m$。 接下来$m$行，每行输入三个整数$u,v,w$，表示一条有向边$u\rightarrow v$，长度为$w$。

输出格式

输出一行一个整数，表示最长路径的长度。

样例输入 #1

3 3
1 3 5
1 2 4
2 3 3

样例输出 #1

7

说明/提示

有$2\leq n\leq 18,1\leq m\leq n(n-1),1\leq w\leq 10^4$。