Trong một dungeon cổ xưa, nhà thám hiểm Aria đang thực hiện một nhiệm vụ quan trọng. Dungeon này bao gồm n hang động (đánh số từ 0 đến n-1) được kết nối với nhau bởi m lối đi bí ẩn. Mỗi cặp hang động chỉ được nối với nhau bởi nhiều nhất một lối đi.

Theo những ghi chép cổ xưa, một báu vật quý giá đang được cất giữ tại hang động n-1. Tuy nhiên, dungeon này chứa đựng một lời nguyền đáng sợ:

Các quái vật cổ xưa sẽ xuất hiện theo một quy luật đặc biệt:

• Với một con số ma thuật p và một tập hợp các số R được khắc trên các bức tường dungeon
• Tại thời điểm t bất kỳ, nếu số dư của t chia cho p (t % p) thuộc tập R, các quái vật sẽ đồng loạt xuất hiện trong tất cả các hang động
• Aria bắt đầu xuất phát ở hang động 0 với t = 0
• Để tránh bị quái vật tấn công, Aria phải liên tục di chuyển và không được dừng lại ở bất kỳ hang động nào

Nhiệm vụ của Aria là tìm ra con đường nhanh nhất từ lối vào dungeon (hang động 0) đến nơi cất giữ báu vật (hang động n-1), trong khi vẫn tránh được những quái vật nguy hiểm.

Input:

• Dòng đầu tiên: ba số nguyên n, m, p (lần lượt là số lượng hang động, số lối đi, và con số ma thuật p)
• Dòng thứ hai: các số thuộc tập R (thời điểm xuất hiện của quái vật)
• M dòng tiếp theo: mỗi dòng gồm ba số nguyên u, v, w trong đó:
• u: hang động xuất phát
• v: hang động đích
• w: thời gian cần để đi qua lối đi

Output:

• In ra -1 nếu không thể đến được hang động chứa báu vật
• Ngược lại, in ra thời gian ngắn nhất để Aria có thể đến được báu vật