시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)88413610320.808%

문제

BOJ 월드에 달리기 대회가 열렸다. BOJ 월드는 $1$부터 $N$까지 번호가 매겨진 정점과 $M$개의 양방향 간선으로 이루어져 있다. 잠시 후 열리는 달리기 대회는 $1$번 정점에서 출발하며, 가장 먼저 $N$번 정점에 도착해 자신의 BOJ 계정에 로그인한 사람이 우승한다. 여러 명이 동시에 가장 먼저 로그인에 성공한다면 그 여러 명이 전부 우승한 것으로 하자.

참가자 lobo_prix는 기억력이 좋지 않아 비밀번호를 노트에 적어두는데, 사악한 참가자 jhnah917는 lobo_prix를 방해하기 위해 그 노트를 찢고 노트 조각을 여기저기 숨겨버렸다. lobo_prix는 비밀번호를 기억하지 못하므로 모든 노트 조각을 수집해서 $N$번 정점으로 가야 한다. jhnah917은 $N$번 정점까지 최단 경로로만 이동한다.

노트 조각을 줍는 시간과 로그인하는 시간은 무시할만하므로 $0$이라 가정하자. 또한 모든 참가자의 이동 속도는 동일하다. lobo_prix가 우승할 수 있는 경로가 있을까?

입력

첫째 줄에 정점의 개수 $N$, 간선의 개수 $M$이 공백을 사이에 두고 입력된다. ($2\leq N \leq 200\,000,\ N-1 \leq M \leq 200\,000$)

다음 $M$개의 줄에 $i$번째 간선이 연결하는 두 정점 $u_i, v_i$와 간선의 길이 $w_i$가 주어진다. ($1\leq u_i,v_i\leq N,\ 1 \leq w_i \leq 10^9,\ u_i \neq v_i,\ w_i$는 정수)

다음 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 주어지며, $i$번 정점에 노트 조각이 존재하면 $A_i=1$, 존재하지 않으면 $A_i=0$이다.

연결하는 정점 쌍이 동일한 간선이 여러 번 주어지지 않으며, $1$번 정점에서 $N$번 정점으로 갈 수 있는 그래프만 주어진다.

출력

lobo_prix가 우승할 수 있는 경로가 없다면 $-1$을 출력한다.

lobo_prix가 우승할 수 있는 경로가 있다면 첫 줄에 방문하는 정점의 개수를 출력하고, 다음 줄에 방문하는 정점을 방문하는 순서대로 공백으로 구분하여 출력한다.

가능한 경로가 여러 개일 경우 그중에 아무거나 하나를 출력하면 된다.

예제 입력 1

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

예제 출력 1

3
1 2 4

예제 입력 2

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

예제 출력 2

-1

예제 입력 3

4 4
1 2 1
2 4 1
1 3 1
3 4 1
1 1 1 1

예제 출력 3

-1