Quartet

역사와 전통을 자랑하는 제271회 UDPC의 개최를 위해 오늘도 수많은 운영진이 동분서주하고 있다. 운영진인 민호는 이전 대회들과 다르게, 개막식을 관현악 사중주로 시작해서 대회에 참여하는 사람들에게 더 풍성한 경험을 주고자 한다.

사중주는 여러 소리가 동시에 어우러져서 조화를 이루는 것이 중요한 만큼, 민호는 연주회의 조화도가 최대가 되도록 네 명의 학생을 선발해서 자리를 배치하려고 한다. 사중주는 네 명의 학생들이 일렬로 앉아서 연주를 진행하는 형태로 이루어진다.

UNIST, DGIST, POSTECH에는 악기를 잘 다루는 학생들이 다 합해서 $N$명이 있고, 이 중 $M$쌍의 학생들 사이에는 시너지가 존재한다. 어떤 시너지에 포함되는 두 학생이 모두 연주회에 참여하고, 두 학생의 연주 위치가 양옆으로 인접하다면 연주회의 조화도가 $d\_i$만큼 상승하게 된다.

민호가 사중주에 참여할 학생들을 고르고 자리를 배치할 수 있는 모든 경우 중, 연주회의 조화도가 최대가 될 때의 그 값을 구해보자.

첫째 줄에는 후보 학생의 수 $N$과 시너지의 수 $M$이 주어진다. $(4\le N\le 200\ 000;0\le M\le 300\ 000)$

둘째 줄부터 $M$개의 줄에 걸쳐 세 정수 $u\_i,v\_i,d\_i$가 공백을 두고 주어진다. $u\_i$번 학생과 $v\_i$번 학생이 인접한 위치에서 연주하면 연주회의 조화도가 $d\_i$만큼 상승한다는 의미이다. 어떤 두 학생 사이의 시너지는 최대 하나만 주어진다. $(1\le u\_i\<v\_i\le N;1\le d\_i\le 10^9)$

입력에서 주어지는 모든 수는 정수이다.

민호가 사중주에 참여할 네 명의 학생들을 고르고, 자리를 정하는 모든 경우 중에서 연주회의 조화도가 최대가 될 때의 값을 출력한다.