Description

小E无意间得到了一张藏宝图。顺着藏宝图的指引，小E找到了藏宝洞的入口。
根据藏宝图的描述，藏宝洞中共有n个洞穴和m条单向通道（单向是因为有一些玄妙的机关），通道有黑白之分，第i条通道由第Xi个洞穴通往第Yi个洞穴，颜色为Wi。通道可能形成重边或自环。藏宝洞的入口在第1个洞穴。
入口处有一个石碑，石碑上记录了找到宝藏的方法。石碑上都是些难懂的话语，什么“秩序”“混沌”“周而复始”之类的，不过这难不倒小E，小E马上就破译了石碑给出的信息：
黑白两种颜色可以分别看作1和0，用以下方式构造一个串01：初始串为一个0,进行无限多次操作，每次将当前串取反后得到的串接在当前串后，最终得到一个无限长的01串。例如，这个串的前几位分别为0110100110010110……
从入口出发，第i步需要走一条与这个01串第i位相同颜色的通道，尽可能地走最多的步数后到达的洞穴既是宝藏所在之地。
由于藏宝图可能出现破损信息错误或是宝藏本身就是假的，可能出现有多个合法的宝藏所在地或是要无限走下去的情况。小E现在只想知道，根据当前信息，她需要多少步才能找到一个合法的宝藏所在地。如果需要的步数超过10^18,小E可能会弃疗。

Format

Input

第一行包含两个非负整数n,m。
接下来行，每行三个非负整数，分别表示xi,yi,wi。

Output

输出一个整数，表示答案，如果答案超过10^18,输出-1。

Sample 1

Input

2 2
1 2 0
2 2 1

Output

3

Sample 2

Input

2 3
1 2 0
2 2 0
2 2 1

Output

-1

Limitation

1s, 512MiB for each test case.
对于前20%的数据，答案不超过10000。
对于前60%的数据，n<=100。
对于100%的数据，1<=n<=500,0<=m<=2*n^2。