새로운 주 나누기

테헤란 주를 알보르즈 주와 뉴테헤란 주 두 개로 나누기로 했다. 옛 테헤란 주에는 도시가 많이 있고, 각 도시는 두 새 주 가운데 한 곳에 속한다. 어느 쪽에 넣을지는 두 주 사이를 오가는 이동의 안전도로 판단한다.

아미르는 옛 테헤란 주의 지도를 받았다. 지도에는 도시와 도로, 그리고 도로마다 정해진 안전도가 적혀 있다. 아미르는 모든 도시를 뉴테헤란과 알보르즈 중 한 곳에 배정한다. 두 도시는 이미 정해져 있다. 테헤란은 뉴테헤란에, 카라지는 알보르즈에 속한다. 한 주가 연결되어 있지 않아도 되므로, 같은 주에 속한 도시라도 서로 오갈 수 없을 수 있다.

아미르는 가장 안전한 분할을 원한다. 분할의 안전도는 드론으로 측정한다. 드론은 두 주 사이를 날면서, 양 끝 도시가 서로 다른 주에 속하는 양방향 도로를 모두 정확히 한 번씩 지난다. 도로를 지날 때마다 그 도로의 안전도를 읽어 전체 안전도를 갱신한다. 도로의 안전도는 센서가 60비트 이진수로 저장하고, 드론도 전체 안전도를 60비트 이진수로 저장한다. 안전도가 $x_{60}x_{59}\dots x_1$인 도로를 지나면, 전체 안전도의 $i$번째 비트는 $x_i$가 1일 때 뒤집히고 아니면 그대로 남는다. 드론이 비행을 마쳤을 때의 전체 안전도가 그 분할의 안전도다. 전체 안전도는 0에서 시작하므로, 두 주를 잇는 도로가 하나도 없으면 값이 바뀌지 않아 분할의 안전도는 0이다.

옛 테헤란 주에는 도시가 $n$개 있고 1번부터 $n$번까지 번호가 붙어 있다. 테헤란이 1번 도시, 카라지가 $n$번 도시다. 어떤 분할로 얻을 수 있는 전체 안전도의 최댓값을 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 도시의 수 $n$과 도로의 수 $m$이 주어진다 ($2 \le n \le 100$, $1 \le m \le n(n-1)/2$). 다음 $m$개 줄에는 각각 세 정수 $u$, $v$, $r$가 주어진다 ($1 \le u, v \le n$, $u \ne v$, $0 \le r < 2^{60}$). 도시 $u$와 도시 $v$를 잇는 도로가 있고 그 안전도가 $r$라는 뜻이다. 두 도시 사이를 잇는 도로는 많아야 하나다. 마지막 줄에는 0이 두 개 주어지며, 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 전체 안전도의 최댓값을 한 줄에 출력한다.