Cvjetko, poznati astronaut, na svojem putu kroz svemir naišao je na Neon galaksiju. Neon galaksija u sebi ima \(n\) planeta određenih boja i svaki planet na sebi ima teleportere odredenih boja. Svaki planet može biti ili crvene ili plave ili zelene boje ili pak može biti proziran. Na planetu može biti više teleportera i svaki je obojan jednom od tri boje: crvenom, zelenom ili plavom. Teleporter ide u jednom smjeru i Cvjetko ga smije iskoristiti samo ako je RAZLIČITO obojan od teleportera. Cvjetko se trenutno nalazi na planetu 1 koji će uvijek biti proziran i želi doći do planeta \(n\). Ako Cvjetko dođe na proziran planet, ne mijenja boju. Ako dođe na obojan planet, onda poprima boju tog planeta. Cvjetka zanima koliko najmanje teleportera treba proći da od planeta \(1\) dođe do planeta \(n\) ako je:

• na početku obojan crvenom bojom,
• na početku obojan zelenom bojom,
• na početku obojan plavom bojom.

Ulaz

U prvom retku nalaze se dva broja \(n\) i \(m\), \((1 \leq n, m \leq 10^5)\) broj planeta i broj teleportera. U sljedećem redu se nalazi \(n\) brojeva \(c_i\), \((0 \leq c_i \leq 3)\), boja \(i\)-tog planeta.

• \(0\) označava da je planet proziran,
• \(1\) označava da je planet obojan crvenom bojom,
• \(2\) označava da je planet obojan zelenom bojom,
• \(3\) označava da je planet obojan plavom bojom.

U sljedećih \(m\) redaka se nalaze po tri broja \(u_i\), \(v_i\), \(k_i\), početni planet, završni planet i boja teleportera. Opet kao i kod planeta, boja \(k_i\), \((1 \leq k_i \leq 3)\) je

• \(1\) ako je teleporter obojan crvenom bojom,
• \(2\) ako je teleporter obojan zelenom bojom,
• \(3\) ako je teleporter obojan plavom bojom.

Ako Cvjetko želi doći s planeta \(u_i\) na planet \(v_i\), NE SMIJE biti obojan bojom \(k_i\).

Izlaz

U jedan redak ispišite tri broja, koliko najmanje teleportera Cvjetko treba iskoristiti da od planeta \(1\) dođe do planeta \(n\) ako je na početku obojan

• crvenom bojom,
• zelenom bojom,
• plavom bojom.

Ako je nemoguće doći od planeta \(1\) do planeta \(n\) s nekom početnom bojom, ispišite \(-1\).

Primjer ulaza

6 7
0 1 0 0 3 2
1 3 1
1 2 1
3 5 1
3 4 2
4 6 2
2 6 1
5 4 2

Primjer izlaza

-1 4 3

Primjer ulaza

3 3
0 1 1
1 3 2
1 2 1
2 1 2

Primjer izlaza

1 3 1