Một thành phố đang triển khai hệ thống giao thông thông minh. Một số tuyến đường được đánh dấu là đường ưu tiên (VIP). Một xe cứu thương cần đi từ nút 1 đến nút N, nhưng do quy định, xe chỉ được đi qua tối đa K tuyến VIP đó (đường đi ở dạng vô hướng).

Yêu cầu: Tìm quãng đường ngắn nhất từ 1 đến N sao cho số tuyến VIP sử dụng không vượt quá K. Nếu không tồn tại đường đi thỏa mãn, in ra -1.

Dữ liệu vào: Cho tệp Input.txt với dữ liệu đầu vào mẫu đã cho bên dưới. - Dòng 1: Ba số nguyên N, M, K (1 ≤ N ≤ 105, 1≤ M ≤ 2 x 105, 0 ≤ K ≤ 20, 1 ≤ W ≤ 109) - M dòng tiếp theo, mỗi dòng gồm 4 số nguyên U, V, W, T (U, V: hai đỉnh của cạnh; W: trọng số cạnh; T = 1 nếu là cạnh VIP, T = 0 nếu là cạnh thường.

Dữ liệu ra: Ghi kết quả ra tệp Output.txt là độ dài đường đi ngắn nhất thỏa mãn yêu cầu. Nếu không tồn tại, in ra -1.

Ví dụ:

Input 1:

4 5 1 1 2 5 0 2 3 5 1 1 3 15 0 3 4 5 0 2 4 20 0

Output 1:

15

Input 2:

3 2 0 1 2 1 1 2 3 1 1

Output 2:

-1

Giải thích test 01: Các đường đi:

1 → 2 → 3 → 4

Trọng số: 5 + 5 + 5 = 15 VIP: 1 cạnh (2→3)

1 → 3 → 4

Trọng số: 15 + 5 = 20 VIP: 0

1 → 2 → 4

Trọng số: 5 + 20 = 25