Đường đi cạnh màu không giảm

Cho đồ thị có hướng $n$ đỉnh, $m$ cạnh. Mỗi cạnh $i$ đi từ $u_i$ tới $v_i$, có màu $c_i$ (số nguyên dương) và trọng số $w_i$ (số nguyên dương).

Một đường đi $u_0\to u_1\to \cdots \to u_k$ được gọi là hợp lệ nếu dãy màu các cạnh dùng theo thứ tự đi là không giảm, tức $c_{e1} \le c{e2} \le \cdots \le c{e_k}$.

Hãy tìm đường đi hợp lệ từ đỉnh $1$ tới đỉnh $n$ có tổng trọng số nhỏ nhất, hoặc kết luận không có.

Dữ liệu vào

• Dòng 1: ba số nguyên $n$, $m$, $C$ — $C$ là cận trên của màu.
• $m$ dòng sau, mỗi dòng bốn số $u_i,v_i,c_i,w_i$.

Dữ liệu ra

In ra tổng trọng số nhỏ nhất, hoặc $-1$ nếu không tồn tại đường đi hợp lệ.

Ràng buộc

• $2\le n\le 2000$
• $1\le m\le 20000$
• $1\le C\le 20$
• $1\le c_i\le C$, $1\le w_i\le {10}^9$
• Có thể có cạnh song song, nhưng không có khuyên ($u_i\ne v_i$).

Ví dụ

Ghi chú

Mở rộng trạng thái thành $(\text{đỉnh},\text{màu cuối cùng})$, áp dụng Dijkstra.