{
TASK:move
LANG:PASCAL
}

PROGRAM MOVE;
TYPE MAS=ARRAY[1..11,1..11]OF INTEGER;
     MAS2=ARRAY[1..11]OF INTEGER;
VAR A:MAS;
    B:MAS2;
    I,J,K,L,N,M,E:INTEGER;
BEGIN
READLN(N,M);
FOR I:=1 TO N DO
FOR J:=1 TO M DO
A[I,J]:=20;
FOR I:=1 TO M DO
BEGIN
READLN(J,K);
A[J,K]:=1;
A[K,J]:=1;
END;
FOR I:=1 TO N DO
READ(B[I]);

FOR I:=1 TO N DO
IF A[I][1]=1 THEN BEGIN E:=I; BREAK END;

FOR K:=1 TO N DO
FOR I:=1 TO N DO
FOR J:=1 TO N DO
{IF (I<>J) THEN}
IF A[I,J]+A[K,I]<A[J,K] THEN
BEGIN
A[J,K]:=A[I,J]+A[K,I];
A[J,K]:=A[K,J];
END;
IF (A[1,1]=0)OR(A[1,1]>19) THEN WRITELN('-1') ELSE WRITELN(A[1,1])



END.