Note Fragments

A running race is held in a world of vertices numbered 1 through $N$, connected by $M$ bidirectional edges. The race starts at vertex $1$. The first person to reach vertex $N$ and log in to their account wins. If several people log in first at the same time, all of them win.

Participant lobo_prix has a poor memory and writes the password on a notebook. The malicious participant jhnah917 tore up the notebook and hid the pieces around the world. lobo_prix cannot remember the password, so lobo_prix must collect every note fragment and then go to vertex $N$. jhnah917 only travels along shortest paths to vertex $N$.

The time to pick up a fragment and the time to log in are negligible, so assume they are $0$. All participants move at the same speed. Is there a path that lets lobo_prix win?

The first line contains the number of vertices $N$ and the number of edges $M$, separated by a space. ($2\leq N \leq 200\,000,\ N-1 \leq M \leq 200\,000$)

Each of the next $M$ lines contains the two vertices $u\_i, v\_i$ connected by the $i$-th edge and its length $w\_i$. ($1\leq u\_i,v\_i\leq N,\ 1 \leq w\_i \leq 10^9,\ u\_i \neq v\_i,\ w\_i$ is an integer)

The next line contains $N$ integers $A\_1, A\_2, \cdots, A\_N$. If vertex $i$ has a note fragment, $A\_i=1$. Otherwise, $A\_i=0$.

No pair of vertices is connected by more than one edge. The graph is given such that vertex $N$ can be reached from vertex $1$.

If there is no path that lets lobo_prix win, print $-1$.

If there is such a path, print the number of visited vertices on the first line. On the next line, print the visited vertices in the order they are visited, separated by spaces.

If several paths are possible, print any one of them.