Po długim czasie rozłąki, Alicja i Bob spotkali się ponownie. Mieszkają w kraju z $n$ miastami, nazwanymi kreatywnie od miasta 1 do miasta $n$. Bob pojechał ze swojego domu w mieście 1 do domu Alicji w mieście $n$.

Kiedy Alicja zapytała Boba, którą drogą jechał, była zdumiona, gdy okazało się, że on tego nie pamięta. Bob jest wydajny, jechał bez zatrzymywania się i wie, że nie ma szybszej drogi niż ta, którą wybrał. Posiada również zupełnie nowy dziennik podróży National Adventuring Company (NAC) TraveLog! Za każdym razem, gdy Bob przejeżdża przez miasto, TraveLog rejestruje czas, jaki upłynął od momentu wyjazdu z miasta 1 do momentu przyjazdu do bieżącego miasta.

W powyższym układzie istnieją dwie możliwe najszybsze ścieżki, którymi Bob może pojechać z miasta 1 do miasta $n$: $1 \to 2 \to 3 \to 5$ lub $1 \to 4 \to 5$. Obie ścieżki zajmują łącznie 9 jednostek czasu. Pierwsza ścieżka miałaby zapis w TraveLogu: 0, 3, 7, 9, a druga: 0, 5, 9.

Niestety, pamięć w TraveLogu Boba uległa uszkodzeniu. Bob uważa, że część czasów zniknęła, a pozostałe zostały dowolnie przemieszane. Czy mając to, co pozostało w TraveLogu, potrafisz odtworzyć ścieżkę Boba?

Wejście

Pierwsza linia wejścia zawiera trzy liczby całkowite $n$ ($2 \le n \le 2 \cdot 10^5$), $m$ ($1 \le m \le 3 \cdot 10^5$) oraz $d$ ($1 \le d \le n$), gdzie $n$ to liczba miast w kraju, $m$ to liczba dróg jednokierunkowych między tymi miastami, a $d$ to liczba czasów pozostałych w uszkodzonym TraveLogu Boba. Miasta są identyfikowane numerami od 1 do $n$. Bob mieszka w mieście 1, a Alicja w mieście $n$.

Każ z kolejnych $m$ linii zawiera trzy liczby całkowite $u, v$ ($1 \le u, v \le n, u \neq v$) oraz $h$ ($1 \le h \le 10^6$). Każda linia opisuje drogę jednokierunkową z miasta $u$ do miasta $v$, której pokonanie zajmuje $h$ jednostek czasu. Gwarantuje się, że istnieje co najmniej jedna ścieżka z miasta 1 do miasta $n$. Między dowolną parą miast może istnieć kilka dróg.

Każda z kolejnych $d$ linii zawiera pojedynczą liczbę całkowitą $t$ ($0 \le t \le 10^{18}$). Jest to to, co pozostało z TraveLogu Boba. Każda linia jest zapisem czasu, jaki zajął Bobowi przejazd z miasta 1 do innego miasta na jego ścieżce. Gwarantuje się, że te wartości są różne.

Wyjście

Format wyjścia zależy od liczby ścieżek zgodnych z TraveLogiem Boba.

• Jeśli nie ma ścieżki zgodnej z TraveLogiem Boba, wypisz 0.
• Jeśli z TraveLogiem Boba zgodnych jest wiele ścieżek, wypisz 1.
• W przeciwnym razie, w pierwszej linii wypisz liczbę miast na ścieżce Boba. W kolejnych liniach wypisz odwiedzone przez Boba miasta, po jednym w linii, w kolejności ich odwiedzania.

Przykład

Wejście 1

5 5 2
1 2 3
2 3 4
3 5 2
1 4 5
4 5 4
5
9

Wyjście 1

3
1
4
5

Wejście 2

6 8 2
1 2 1
2 3 2
3 6 8
1 4 3
4 5 4
5 6 4
5 2 7
1 6 13
0
3

Wyjście 2

1

Wejście 3

2 1 1
1 2 10
5

Wyjście 3

0