Đất nước ABC có \(n\) thành phố và \(m\) con đường một chiều. Con đường thứ \(i\) nối hai thành phố \(u_i\) và \(v_i\) với nhau, có độ dài \(l_i\) và có chi phí \(t_i\).

\(H\) là một du khách. Hiện tại, anh đang ở thành phố \(1\) và cần đi tới thành phố \(n\). Tuy nhiên anh ta chỉ mang đúng \(K\) đồng tiền.

Hãy giúp \(H\) tính toán lộ trình ngắn nhất từ thành phố \(1\) tới \(n\) mà chỉ mất tổng chi phí ít hơn hoặc bằng \(K\).

Input

• Dòng thứ nhất chứa \(2\) số nguyên dương \(n, m\).
• Dòng thứ hai chứa số nguyên dương \(K\).
• \(m\) dòng sau mỗi dòng gồm \(4\) số nguyên dương \(u_i, v_i, l_i, t_i\) \((1 \le u, v \le n, u \neq v)\), miêu tả con đường nối thành phố \(u_i\) với \(v_i\) có độ dài \(l_i\) và chi phí \(t_i\).

Output

• In ra độ dài đường đi ngắn nhất từ \(1\) tới \(n\) mà tổng chi phí không quá \(K\).
• Nếu không có lộ trình nào để đi từ \(1\) tới \(n\) và tiêu không quá \(K\), in ra \(-1\).

Constraints

• \(1 \le n \le 100\).
• \(1 \le m \le 1000\).
• \(1 \le k \le 10000\).
• \(1 \le l_i \le 1000\).
• \(0 \le t_i \le 1000\).

Subtasks

• Subtask \(1\): \(1 \le n,m \le 20\) (30%)
• Subtask \(2\): Không có ràng buộc gì thêm (70%)

Sample Input 1

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

Sample Output 1

11

Explanation 1

Đi theo lộ trình \((1,3,5,4,6)\).

Sample Input 2

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

Sample Output 2

-1

Explanation 2

Không có lộ trình nào để đi từ \(1\) tới \(4\) tiêu không quá \(0\).

Bạn dự định đi từ Syrjälä đến Lehmälä bằng máy bay. Hãy trả lời các câu hỏi sau:

• Giá rẻ nhất của một lộ trình như vậy là bao nhiêu?
• Có bao nhiêu lộ trình với giá rẻ nhất? (chia lấy dư cho \(10^9 + 7\))
• Số lượng chuyến bay tối thiểu của một lộ trình với giá rẻ nhất là bao nhiêu?
• Số lượng chuyến bay tối đa của một lộ trình với giá rẻ nhất là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng thành phố và chuyến bay.
  Các thành phố được đánh số \(1, 2, \ldots, n\). Thành phố \(1\) là Syrjälä, và thành phố \(n\) là Lehmälä.
• Sau đó có \(m\) dòng, mỗi dòng gồm ba số nguyên \(a, b, c\): có một chuyến bay một chiều từ \(a\) đến \(b\) với giá \(c\).
• Bảo đảm tồn tại ít nhất một lộ trình từ Syrjälä đến Lehmälä.

Output

• In ra bốn số nguyên theo thứ tự:
  (1) giá rẻ nhất,
  (2) số lộ trình có giá rẻ nhất (mod \(10^9+7\)),
  (3) số chuyến bay tối thiểu trong số các lộ trình rẻ nhất,
  (4) số chuyến bay tối đa trong số các lộ trình rẻ nhất.

Constraints

• \(1 \le n \le 10^5\)
• \(1 \le m \le 2 \cdot 10^5\)
• \(1 \le a, b \le n\)
• \(1 \le c \le 10^9\)

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

5 2 1 2

Có \(n\) thành phố và \(m\) con đường hai chiều. Cần vận chuyển các mặt hàng thiết yếu từ thành phố \(1\) tới tất cả các thành phố khác (việc vận chuyển tới các thành phố khác luôn thực hiện được).

Mỗi con đường đều có thu phí. May mắn thay, bạn có \(k\) thẻ ưu đãi, nghĩa là khi đi từ thành phố \(1\) tới bất kỳ thành phố nào khác, bạn có thể chọn tối đa \(k\) con đường và không bị tính phí khi đi qua các con đường đó.

Hãy xác định chi phí tối thiểu để chuyển hàng tới mỗi thành phố. Lưu ý có thể xem việc vận chuyển từ thành phố \(1\) tới các thành phố khác là độc lập nhau.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, k\) \((1 \leq n \leq 10^{5},\ 1 \leq m \leq 5 \times 10^{5},\ 1 \leq k \leq 18)\).
• \(m\) dòng tiếp theo, mỗi dòng chứa \(3\) số nguyên \(u, v, w\) \((1 \leq u, v \leq n,\ 1 \leq w \leq 10^{6})\) mô tả một con đường hai chiều nối \(u, v\) với chi phí \(w\).

Output

• In \(n\) số nguyên, số thứ \(i\) là chi phí tối thiểu để vận chuyển tới thành phố \(i\).

Example

5 6 1
1 2 2
1 3 6
2 4 6
2 5 8
3 5 4
4 5 1

0 0 0 2 2

Định nghĩa \(f(x)\) là tổng các chữ số của số nguyên \(x\). Cho số nguyên \(k\), hãy tìm giá trị \(f(x)\) nhỏ nhất có thể khi xét các số nguyên dương \(x\) chia hết cho \(k\).

Input

• Gồm một số nguyên \(2 \le k \le 100000\).

Output

• In ra giá trị \(f(x)\) nhỏ nhất.

Sample Test

6

3