暂无测试数据。

$n$ 个学生将要坐车去餐厅，每辆车最多可以坐 $5$ 个人并且出于对环境的考虑他们不会使用多余的车.车的速度为每秒 $1$ 个单位。现在 $i$ 号同学需要去 $i$ 号点停 $5$ 分钟（此时整车都在 $i$ 号点等待），他们现在希望最小化花费时间最长的车花费的时间. $0$ 号点为起点，$n+1$ 号点为餐厅

输入格式

第一行两个整数分别表示 $n,m$

接下来 $m$ 行每行三个整数分别是 $u,v,w$，表示这条路连接 $u,v$ 长度为 $w$

输出格式

输出花费时间最长的车花费时间最小为多少

数据范围

对于 $30\%$ 的数据, $1 \leq n \leq 5$

对于 $50\%$ 的数据, $1 \leq n \leq 10$

对于 $100\%$ 的数据, $1 \leq n \leq 15,1 \leq m \leq 1000,0 \leq u,v \leq n+1,1 \leq w \leq 10^7$

7 15
0 1 100
8 1 100
0 2 100
8 2 100
0 3 100
8 3 100
0 3 50
3 4 50
3 5 40
1 5 50
5 6 20
1 6 20
3 6 10
6 7 10
7 8 10

280