CF780F.Axel and Marston in Bitland

A couple of friends, Axel and Marston are travelling across the country of Bitland. There are n towns in Bitland, with some pairs of towns connected by one-directional roads. Each road in Bitland is either a pedestrian road or a bike road. There can be multiple roads between any pair of towns, and may even be a road from a town to itself. However, no pair of roads shares the starting and the destination towns along with their types simultaneously.

The friends are now located in the town 1 and are planning the travel route. Axel enjoys walking, while Marston prefers biking. In order to choose a route diverse and equally interesting for both friends, they have agreed upon the following procedure for choosing the road types during the travel:

• The route starts with a pedestrian route.
• Suppose that a beginning of the route is written in a string s of letters P (pedestrain road) and B (biking road). Then, the string is appended to s, where stands for the string s with each character changed to opposite (that is, all pedestrian roads changed to bike roads, and vice versa).

In the first few steps the route will look as follows: P, PB, PBBP, PBBPBPPB, PBBPBPPBBPPBPBBP, and so on.

After that the friends start travelling from the town 1 via Bitlandian roads, choosing the next road according to the next character of their route type each time. If it is impossible to choose the next road, the friends terminate their travel and fly home instead.

Help the friends to find the longest possible route that can be travelled along roads of Bitland according to the road types choosing procedure described above. If there is such a route with more than 1018 roads in it, print -1 instead.

几位朋友——阿克塞尔（Axel）和马斯顿（Marston）——正在比特兰（Bitland）国家旅行。比特兰共有 $n$ 座城镇，其中某些城镇对之间由有向道路连接。比特兰的每条道路要么是人行道，要么是自行车道。任意两座城镇之间可能存在多条道路，甚至可能存在从一座城镇指向其自身的道路。然而，不存在两条道路同时具有相同的起点、终点和类型。

目前，这两位朋友位于第 1 号城镇，并正规划他们的旅行路线。阿克塞尔喜欢步行，而马斯顿更偏爱骑车。为了确保路线对两位朋友而言都丰富多样且同样有趣，他们约定采用如下规则来确定旅途中各段道路的类型：

• 路线以一条人行道开始；
• 假设当前路线的开头部分已表示为一个由字母 P（人行道）和 B（自行车道）组成的字符串 $s$，则将字符串 追加到 $s$ 后面，其中 表示将字符串 $s$ 中每个字符取反后得到的新字符串（即所有 P 变为 B，所有 B 变为 P）。

在前几步中，该路线依次为：P、PB、PBBP、PBBPBPPB、PBBPBPPBBPPBPBBP，依此类推。

随后，朋友们从第 1 号城镇出发，沿比特兰的道路旅行，每次根据上述生成规则所得路线字符串中的下一个字符，选择对应类型的下一段道路。若此时无法选出符合要求的下一段道路，则旅行终止，他们直接乘飞机回家。

请帮助这两位朋友找出：依据上述道路类型选择规则，能够在比特兰道路上走过的最长可能路线。如果存在长度超过 $10^{18}$ 条道路的可行路线，请输出 -1。

The first line contains two integers n and m (1 ≤ n ≤ 500, 0 ≤ m ≤ 2_n_2) — the number of towns and roads in Bitland respectively.

Next m lines describe the roads. i-th of these lines contains three integers v__i, u__i and t__i (1 ≤ v__i, u__i ≤ n, 0 ≤ t__i ≤ 1), where v__i and u__i denote start and destination towns indices of the i-th road, and t__i decribes the type of i-th road (0 for a pedestrian road, 1 for a bike road). It is guaranteed that for each pair of distinct indices i, j such that 1 ≤ i, j ≤ m, either v__i ≠ v__j, or u__i ≠ u__j, or t__i ≠ t__j holds.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 500$，$0 \leq m \leq 2n^2$），分别表示 Bitland 中的城镇数量和道路数量。

接下来的 $m$ 行描述了这些道路。其中第 $i$ 行包含三个整数 $v_i$、$u_i$ 和 $t_i$（$1 \leq v_i, u_i \leq n$，$0 \leq t_i \leq 1$），其中 $v_i$ 和 $u_i$ 分别表示第 $i$ 条道路的起点与终点城镇编号，$t_i$ 表示第 $i$ 条道路的类型（$0$ 表示人行道，$1$ 表示自行车道）。保证对于任意两个不同的下标 $i, j$（$1 \leq i, j \leq m$），均有 $v_i \neq v_j$ 或 $u_i \neq u_j$ 或 $t_i \neq t_j$ 成立。

If it is possible to find a route with length strictly greater than 1018, print -1. Otherwise, print the maximum length of a suitable path.

如果可以找到一条长度严格大于 $10^{18}$ 的路径，则输出 -1；否则，输出满足条件的路径的最大长度。

In the first sample we can obtain a route of length 3 by travelling along the road 1 from town 1 to town 2, and then following the road 2 twice from town 2 to itself.

In the second sample we can obtain an arbitrarily long route by travelling the road 1 first, and then choosing road 2 or 3 depending on the necessary type.

在第一个样例中，我们可以通过以下方式得到一条长度为 3 的路径：先沿道路 1 从城镇 1 到城镇 2，再沿道路 2 从城镇 2 到自身两次。

在第二个样例中，我们可以通过以下方式得到任意长的路径：首先沿道路 1 行进，然后根据所需类型选择道路 2 或道路 3。