New Country Division

Tehran province is being divided into two provinces, Alborz and New Tehran. The old Tehran province contains many cities, and every city joins one of the two new provinces. The division is judged by the safety of travel between the two provinces.

Amir has the map of the old Tehran province with its cities, its roads, and a safety value for each road. He assigns every city to either New Tehran or Alborz. Two cities are already fixed: Tehran belongs to New Tehran, and Karaj belongs to Alborz. A province does not have to be connected, so one of its cities may be unreachable from another city of the same province.

Amir wants the safest possible division. The safety of a division is measured by a drone. The drone flies between the two provinces and crosses every bidirectional road whose two endpoints lie in different provinces exactly once. Each time it passes a road, it reads the safety of that road and updates the overall safety. A sensor stores the safety of a road as a 60-bit binary number, and the drone stores the overall safety as a 60-bit binary number as well. After the drone passes a road with safety $x_{60}x_{59}\dots x_1$, bit $i$ of the overall safety flips when $x_i$ equals 1 and stays unchanged otherwise. The safety of the division is the overall safety after the drone finishes its flight. The overall safety starts at zero, so when no road joins the two provinces it never changes and the division has safety 0.

The old Tehran province has $n$ cities numbered 1 to $n$. Tehran is city 1 and Karaj is city $n$. Write a program that reports the largest overall safety any division can reach.

The input contains several test cases. The first line of each test case has two integers $n$ and $m$ ($2 \le n \le 100$, $1 \le m \le n(n-1)/2$), the number of cities and the number of roads. Each of the next $m$ lines has three integers $u$, $v$ and $r$ ($1 \le u, v \le n$, $u \ne v$, $0 \le r < 2^{60}$), meaning that a road connects city $u$ and city $v$ and its safety is $r$. At most one road connects any pair of cities. The last line contains two zeros and is not a test case.

For each test case, print one line with the maximum overall safety.