伟大的自行车比赛即将到来，这意味着年度主要体育赛事的组织者们需要为参赛者选择赛道。

该国由 $n$ 个城市和 $m$ 条双向道路组成。其中一个城市将被选为比赛的主办城市。伟大的自行车比赛为期两天。在这两天的每一天里，骑手们将从主办城市出发，经过两个中间城市，然后返回主办城市。这两天所经过的中间城市不能重复。这意味着伟大的自行车比赛总共经过 5 个不同的城市和 6 条不同的道路。

为了选择最有趣的比赛路线，组织者利用 Yandex 关于道路的数据和现代机器学习技术，为每条道路分配了一个整数，定义了其吸引力 $a_i$。整个比赛路线的吸引力计算为所有 6 条道路的吸引力值之和。

在掌握了这些信息后，请找出是否有可能举办满足上述路线要求的比赛，如果可以，请确定该路线的最大可能吸引力值。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($5 \le n \le 100\,000$, $6 \le m \le 100\,000$)，分别表示城市数量和道路数量。

接下来的 $m$ 行，每行包含三个整数 $u_i, v_i$ 和 $a_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le a_i \le 100\,000$)：表示该道路连接的两个城市及其吸引力值。没有两条道路连接同一对城市。

输出格式

如果没有合法的路线，输出 $-1$。否则，打印合法路线的最大总吸引力值。

样例

样例输入 1

6 9
1 2 3
2 3 1
3 4 2
4 5 1
3 5 7
2 5 2
1 5 3
4 6 2
5 6 1

样例输出 1

18

样例输入 2

6 6
1 3 2
1 2 2
2 3 4
3 4 1
3 6 6
1 4 8

样例输出 2

-1

说明

在第一个样例中，最佳选择之一是将城市 5 选为主办城市，比赛路线为城市序列 $5 \to 1 \to 2 \to 5 \to 3 \to 4 \to 5$。