Son Goku là một chiến binh Saiyan quả cảm với niềm đam mê võ thuật bất tận và trái tim luôn sẵn sàng bảo vệ hòa bình vũ trụ. Trong cuộc hành trình tìm kiếm Bảy Viên Ngọc Rồng trên hành tinh Namek để hồi sinh những người đồng đội đã ngã xuống, Goku phải di chuyển từ căn cứ xuất phát của nhóm Bulma đến vùng đất linh thiêng của Quốc Trưởng Guru. Qua chiếc máy Radar Ngọc Rồng do Bulma chế tạo, toàn bộ địa hình hành tinh Namek hiện lên như một mạng lưới các hòn đảo liên kết chặt chẽ với nhau. Tuy nhiên, đội quân của bạo chúa Frieza đang ráo riết tuần tra và sẵn sàng phong tỏa bất kỳ khu vực nào để chặn đường Goku.

Để giúp Goku giữ sức cho trận chiến quyết định, Bulma quyết định lập trình một hệ thống dẫn đường thông minh trên Radar dựa trên cấu trúc bản đồ:

• Cấu trúc bản đồ hành tinh Namek:
  • Hệ thống địa hình gồm ~N~ khu vực được đánh số thứ tự từ ~1~ đến ~N~, trong đó khu vực ~1~ là căn cứ xuất phát và khu vực ~N~ là nơi ở của Quốc Trưởng Guru.
  • Có ~M~ tuyến đường bay hai chiều nối giữa các khu vực. Tuyến đường thứ ~i~ kết nối trực tiếp hai khu vực ~u~ và ~v~ với khoảng cách di chuyển là một số nguyên dương ~w~.

• Quy tắc cảnh báo của Radar: Trước sự truy lùng của quân đoàn Frieza, Bulma đặt ra ~Q~ kịch bản khẩn cấp cần phải tính toán trước:
  • Mỗi kịch bản được đại diện bởi một số nguyên dương ~x~, giả định rằng khu vực ~x~ (cùng toàn bộ các tuyến đường kết nối trực tiếp với ~x~) đã bị Frieza phong tỏa hoàn toàn và Goku không thể đi qua đó.
  • Nhiệm vụ của hệ thống là phải tìm ra độ dài đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~N~ nếu loại bỏ đỉnh ~x~ khỏi đồ thị.

Tình thế trên hành tinh Namek đang vô cùng cấp bách khi khí của Frieza ngày càng tiến lại gần. Bạn hãy lập trình giúp Bulma và Son Goku tìm ra lộ trình tối ưu cho toàn bộ ~Q~ kịch bản này nhé!

Input

• Dòng đầu tiên chứa ba số nguyên dương ~N, M~ và ~Q~, lần lượt là số lượng khu vực, số lượng tuyến đường bay và số lượng kịch bản giả định ~(N,Q \leq 10^5; M \leq 2\times10^5)~.
• ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~u, v~ và ~w~ thể hiện tuyến đường hai chiều nối giữa đỉnh ~u~ và đỉnh ~v~ có trọng số ~w~ ~(1 \leq u, v \leq N; w \leq 10^9)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~x~ thể hiện khu vực bị loại bỏ trong kịch bản tương ứng ~(1 \leq x \leq N)~.

Output

• Gồm ~Q~ dòng, mỗi dòng in ra một số nguyên duy nhất là độ dài đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~N~ khi loại bỏ đỉnh ~x~ tương ứng. Nếu không tồn tại đường đi, in ra ~-1~.

Example Input

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

Example Output

7
8

Giải thích

• Ban đầu, đồ thị có ~2~ lộ trình chính từ đỉnh ~1~ đến đỉnh ~5~:
  • Lộ trình ~1 \rightarrow 2 \rightarrow 4 \rightarrow 5~ có tổng trọng số là ~3 + 3 + 2 = 8~.
  • Lộ trình ~1 \rightarrow 3 \rightarrow 5~ có tổng trọng số là ~5 + 2 = 7~.
• Truy vấn 1 (2): Nếu loại bỏ đỉnh ~2~, lộ trình đi qua đỉnh ~2~ bị chặn. Đường đi ngắn nhất từ ~1~ đến ~5~ lúc này là ~1 \rightarrow 3 \rightarrow 5~ với tổng trọng số là ~7~.
• Truy vấn 2 (3): Nếu loại bỏ đỉnh ~3~, lộ trình đi qua đỉnh ~3~ bị chặn. Đường đi ngắn nhất từ ~1~ đến ~5~ lúc này là ~1 \rightarrow 2 \rightarrow 4 \rightarrow 5~ với tổng trọng số là ~8~.

Ràng buộc

• Subtask ~1~ (~15\%~ số điểm): ~N \leq 100~ và ~Q = 1~.
• Subtask ~2~ (~15\%~ số điểm): ~N \leq 100~ và ~Q \leq 100~.
• Subtask ~3~ (~15\%~ số điểm): ~N \leq 1000~ và ~Q = 1~.
• Subtask ~4~ (~15\%~ số điểm): ~N \leq 1000~ và ~Q \leq 100~.
• Subtask ~5~ (~15\%~ số điểm): Đồ thị đã cho là một cây.
• Subtask ~6~ (~5\%~ số điểm): ~Q \leq 100~ và ~w = 1~.
• Subtask ~7~ (~5\%~ số điểm): ~N \leq 2000~ và ~Q \leq 10^5~.
• Subtask ~8~ (~5\%~ số điểm): ~N \leq 5 \times 10^4~ và ~Q \leq 1000~.
• Subtask ~9~ (~5\%~ số điểm): Số giá trị ~x~ khác nhau trong tất cả các truy vấn ~\leq 100~ và ~N, Q \leq 10^5~.
• Subtask ~10~ (~5\%~ số điểm): Không có ràng buộc gì thêm.