PROGRAMMING:YP's spaceship
YP likes traveling very much
As we all know, in the world of small K, there are two parallel universes. The two parallel universes are a and B. a universe has n cities and M1 roads, B universe has n cities and M2 roads. The number of cities is 1 ~ n
YP is now in City 1 of parallel universe A. he wants to go to city n of parallel universe B
YP has a spaceship, spaceship has a magic function, it can take you from any point of a parallel universe to the corresponding point of B parallel universe
For example, YP is now in city 3 of parallel universe a, and it can jump to city 3 of parallel universe B. But because YP is not so rich, the spaceship he bought can only shuttle through the parallel universe once.
What is the shortest distance from city 1 of parallel universe a to city n of parallel universe B
###Input format:
Enter a row of N, M1, M2 to represent the number of roads of n cities and two parallel universes
$$1<=n<=500000$$,$$1<=m1,m2<=1000000$$.
Next, there are three numbers a, B and C in line M1, which means that there is a two-way road from point a to point B (a can go to B, B can go to a) in parallel universe;
Next, there are three numbers a, B, C in line m2, which means that there is a two-way road from point a to point B (a can go to B, B can go to a);
$$1<=a,b<=n$$,$$1<=c<=1000000000$$.
###Output format:
Output a line of an integer, the shortest distance, if YP can not complete his trip, then output - 1
###Input example:
Here is a set of inputs. For example:
```in
3 2 2
1 2 1
2 3 2
1 2 2
2 3 1
```
###Output example:
The corresponding output is given here. For example:
```out
two
```
###tips
The input road data may have double edge and self loop（ Double edge means that there are multiple edges from a to B, and self ring means that there is a direct edge from a to a
answer：If there is no answer, please comment
As we all know, in the world of small K, there are two parallel universes. The two parallel universes are a and B. a universe has n cities and M1 roads, B universe has n cities and M2 roads. The number of cities is 1 ~ n
YP is now in City 1 of parallel universe A. he wants to go to city n of parallel universe B
YP has a spaceship, spaceship has a magic function, it can take you from any point of a parallel universe to the corresponding point of B parallel universe
For example, YP is now in city 3 of parallel universe a, and it can jump to city 3 of parallel universe B. But because YP is not so rich, the spaceship he bought can only shuttle through the parallel universe once.
What is the shortest distance from city 1 of parallel universe a to city n of parallel universe B
###Input format:
Enter a row of N, M1, M2 to represent the number of roads of n cities and two parallel universes
$$1<=n<=500000$$,$$1<=m1,m2<=1000000$$.
Next, there are three numbers a, B and C in line M1, which means that there is a two-way road from point a to point B (a can go to B, B can go to a) in parallel universe;
Next, there are three numbers a, B, C in line m2, which means that there is a two-way road from point a to point B (a can go to B, B can go to a);
$$1<=a,b<=n$$,$$1<=c<=1000000000$$.
###Output format:
Output a line of an integer, the shortest distance, if YP can not complete his trip, then output - 1
###Input example:
Here is a set of inputs. For example:
```in
3 2 2
1 2 1
2 3 2
1 2 2
2 3 1
```
###Output example:
The corresponding output is given here. For example:
```out
two
```
###tips
The input road data may have double edge and self loop（ Double edge means that there are multiple edges from a to B, and self ring means that there is a direct edge from a to a
answer：If there is no answer, please comment