노트 조각

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

참가자 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$을 출력한다.

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

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