Dijsktra

Có \(n\) thành phố và \(m\) chuyến bay giữa chúng. Nhiệm vụ của bạn là xác định độ dài của tuyến đường ngắn nhất từ ​​Syrjälä đến mọi thành phố.

Input

• Dòng đầu vào đầu tiên có 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\) và thành phố \(1\) là Syrjälä.
• Sau đó, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên \(a\), \(b\) và \(c\): một chuyến bay bắt đầu tại thành phố \(a\), kết thúc tại thành phố \(b\), và độ dài của nó là \(c\). Mỗi chuyến bay là một chuyến bay một chiều.
• Bạn có thể giả định rằng có thể đi từ Syrjälä đến tất cả các thành phố khác.

Constraints

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

Output

• In \(n\) số nguyên: độ dài tuyến đường ngắn nhất từ ​​Syrjälä đến các thành phố \(1,2,\ldots,n\).

Example

3 4
1 2 6
1 3 2
3 2 3
1 3 4

0 5 2

Có \(n\) thành phố và \(m\) con đường giữa chúng. Nhiệm vụ của bạn là hãy xử lý \(q\) truy vấn mà trong đó bạn phải xác định độ dài của tuyến đường ngắn nhất giữa hai thành phố cho trước.

Input

• Dòng đầu vào đầu tiên có ba số nguyên \(n\), \(m\) và \(q\): số lượng thành phố, con đường và truy vấn
• Sau đó, có \(m\) dòng mô tả các con đường. Mỗi dòng có ba số nguyên \(a\), \(b\) và \(c\): có một con đường giữa các thành phố \(a\) và \(b\) mà độ dài của nó là \(c\). Tất cả con đường đều là con đường hai chiều
• Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng có hai số nguyên \(a\) và \(b\): xác định độ dài của tuyến đường ngắn nhất giữa các thành phố \(a\) và \(b\)
• Các ràng buộc:
  • \(1 \leq n \leq 500\)
  • \(1 \leq m \leq n^2\)
  • \(1 \leq q \leq 10^5\)
  • \(1 \leq a,b \leq n\)
  • \(1 \leq c \leq 10^9\)

Output

• In độ dài của tuyến đường ngắn nhất với mỗi truy vấn. Nếu không có tuyến đường nào, in \(-1\) thay vào đó

Example

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

5
5
8
-1
3

Bạn được cho một đồ thị có hướng, và nhiệm vụ của bạn là hãy xác định xem đồ thị đó có chứa một chu trình âm hay không, và đồng thời cho một ví dụ của một chu trình như vậy.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng nút và cạnh. Các nút được đánh số \(1, 2, \ldots, n\)
• Sau này, có \(m\) dòng mô tả các cạnh. Mỗi dòng có ba số nguyên \(a\), \(b\), và \(c\): có một cạnh từ nút \(a\) đến nút \(b\) mà độ dài của nó là \(c\)

Constraints

• \(1 \leq n \leq 2500\)
• \(1 \leq m \leq 5000\)
• \(1 \leq a,b \leq n\)
• \(-10^9 \leq c \leq 10^9\)

Output

• Nếu đồ thị chứa một chu trình âm, đầu tiên in ra YES, và sau đó là các nút trong chu trình theo thứ tự của chúng. Nếu có vài chu trình âm, bạn có thể in bất kì trong số chúng. Nếu không có chu trình âm, in ra NO

Example

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

YES
1 2 4 1

Bạn chơi một trò chơi gồm \(n\) căn phòng và \(m\) đường hầm. Số điểm ban đầu của bạn là \(0\), và mỗi đường hầm tăng số điểm của bạn thêm \(x\) mà trong đó \(x\) có thể dương hoặc âm. Bạn có thể đi qua một đường hầm vài lần.

Nhiệm vụ của bạn là đi bộ từ phòng \(1\) đến phòng \(n\). Số điểm tối đa mà bạn có thể đạt được là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng phòng và đường hầm. Các phòng được đánh số \(1, 2, \ldots, n\)
• Sau đó, có \(m\) dòng mô tả các đường hầm. Mỗi dòng có ba số nguyên \(a\), \(b\) và \(x\): đường hầm bắt đầu tại phòng \(a\), kết thúc tại phòng \(b\), và tăng số điểm của bạn thêm \(x\). Tất cả đường hầm đều là đường hầm một chiều
• Bạn có thể giả định rằng luôn có thể đi từ phòng \(1\) đến phòng \(n\)

Constraints

• \(1 \le n \le 2500\)
• \(1 \le m \le 5000\)
• \(1 \le a,b \le n\)
• \(-10^9 \le x \le 10^9\)

Output

• In một số nguyên: số điểm lớn nhất bạn có thể đạt được. Tuy nhiên, nếu bạn có thể đạt được số điểm lớn tùy ý, hãy in \(-1\)

Example

4 5
1 2 3
2 4 -1
1 3 -2
3 4 7
1 4 4

5

Nhiệm vụ của bạn là tìm một lộ trình bay rẻ nhất từ Syrjälä đến Metsälä. Bạn có một phiếu khuyến mãi, sử dụng nó có thể giảm một nửa giá của bất kỳ chuyến bay nào trong suốt lộ trình. Tuy nhiên, bạn chỉ có thể sử dụng phiếu đó một lần.

Input

• Dòng đầu vào đầu tiên có 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à Metsälä.
• Sau này, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên \(a\), \(b\) và \(c\): một chuyến bay bắt đầu tại thành phố \(a\), kết thúc tại thành phố \(b\), và giá của nó là \(c\). Mỗi chuyến bay đều là một chiều.
• Bạn có thể giả định rằng luôn luôn có thể đi từ Syrjälä đến Metsälä.

Output

• In một số nguyên: giá của lộ trình rẻ nhất từ Syrjälä đến Metsälä.
• Khi bạn sử dụng phiếu khuyến mãi cho một chuyến bay mà giá tiền của nó là \(x\), giá tiền của nó trở thành \(\lfloor x/2 \rfloor\) (làm tròn xuống một số nguyên).

Constraints

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

Example

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

2

Nhiệm vụ của bạn là tìm \(k\) lộ trình bay ngắn nhất từ Syrjälä đến Metsälä. Một lộ trình có thể đi qua một thành phố vài lần.

Lưu ý rằng có thể có một số lộ trình với cùng một mức giá và mỗi lộ trình nên được xét (xem ví dụ).

Input

• Dòng đầu vào đầu tiên có ba số nguyên \(n\), \(m\), và \(k\): số lượng thành phố, chuyến bay, và tham số \(k\). 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à Metsälä.
• Sau này, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên \(a\), \(b\), và \(c\): chuyến bay bắt đầu tại thành phố \(a\), kết thúc tại thành phố \(b\), và giá của nó là \(c\). Tất cả các chuyến bay đều là chuyến bay một chiều.
• Bạn có thể giả định rằng có ít nhất \(k\) lộ trình phân biệt từ Syrjälä đến Metsälä.

Constraints

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

Output

• In \(k\) số nguyên: giá của \(k\) tuyến đường rẻ nhất được sắp xếp theo giá của chúng.

Example

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

4 4 7