Đường đi ngắn nhất giữa mọi cặp đỉnh

Nguồn: Luogu

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một đồ thị có hướng gồm $n$ đỉnh và $m$ cạnh có trọng số. Các đỉnh được đánh số từ $1$ đến $n$.

Mỗi cạnh có dạng $(u,v,w)$, biểu diễn một cạnh có hướng đi từ đỉnh $u$ đến đỉnh $v$ với trọng số $w$.

Độ dài của một đường đi được định nghĩa là tổng trọng số của tất cả các cạnh thuộc đường đi đó.

Với mọi cặp đỉnh $(i,j)$, gọi $dis_{i,j}$ là độ dài đường đi ngắn nhất từ đỉnh $i$ đến đỉnh $j$.

Đồ thị có thể chứa:

• cạnh có trọng số âm;
• nhiều cạnh cùng đi từ một đỉnh đến một đỉnh khác;
• cạnh khuyên.

Nếu tồn tại một chu trình có tổng trọng số âm trong đồ thị, đồ thị được coi là chứa chu trình âm.

Một số bộ dữ liệu được thiết kế đặc biệt để kiểm tra nghiêm ngặt các cài đặt không đủ hiệu quả khi xử lý lặp lại bài toán đường đi ngắn nhất từ từng đỉnh.

Input

Dòng đầu tiên chứa hai số nguyên $n,m$, lần lượt là số đỉnh và số cạnh có hướng của đồ thị.

Trong $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u,v,w$, biểu diễn một cạnh có hướng từ đỉnh $u$ đến đỉnh $v$ với trọng số $w$.

Output

Nếu đồ thị chứa chu trình âm, chỉ in ra một dòng:

-1

Ngược lại, in ra $n$ dòng.

Ở dòng thứ $i$, in giá trị

$$\sum_{j=1}^{n} j\cdot dis_{i,j}.$$

Trong đó:

• nếu tồn tại đường đi từ $i$ đến $j$, $dis_{i,j}$ là độ dài đường đi ngắn nhất từ $i$ đến $j$;
• nếu không tồn tại đường đi từ $i$ đến $j$, quy ước $dis_{i,j}=10^9$;
• nếu $i=j$, quy ước $dis_{i,i}=0$.

Giá trị cần in có thể vượt quá phạm vi của số nguyên có dấu $32$ bit.

Subtask

• Trong tất cả các Subtask: $1\le n\le3\cdot10^3$; $1\le m\le6\cdot10^3$; $1\le u,v\le n$; $-3\cdot10^5\le w\le3\cdot10^5$.

• Subtask 1 — 20%: $1\le n\le100$; đồ thị không chứa chu trình âm.

• Subtask 2 — 20%: $0\le w\le3\cdot10^5$.

• Subtask 3 — 60%: $1\le n\le3\cdot10^3$; $1\le m\le6\cdot10^3$; $1\le u,v\le n$; $-3\cdot10^5\le w\le3\cdot10^5$.

Ví dụ

Ví dụ 1

Input

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

Output

128
1000000072
999999978
1000000026
1000000014

Giải thích

Đồ thị không chứa chu trình âm.

Ma trận khoảng cách ngắn nhất giữa các cặp đỉnh là:

$$\begin{pmatrix} 0 & 4 & 11 & 8 & 11\\ 10^9 & 0 & 7 & 4 & 7\\ 10^9 & -5 & 0 & -3 & 0\\ 10^9 & -2 & 5 & 0 & 3\\ 10^9 & -1 & 4 & 1 & 0 \end{pmatrix}.$$

Với đỉnh $1$:

$$1\cdot0+2\cdot4+3\cdot11+4\cdot8+5\cdot11=128.$$

Với đỉnh $2$, không tồn tại đường đi đến đỉnh $1$, nên $dis_{2,1}=10^9$. Do đó:

$$1\cdot10^9+2\cdot0+3\cdot7+4\cdot4+5\cdot7 =1000000072.$$

Tương tự:

$$1\cdot10^9+2\cdot(-5)+3\cdot0+4\cdot(-3)+5\cdot0 =999999978,$$$$1\cdot10^9+2\cdot(-2)+3\cdot5+4\cdot0+5\cdot3 =1000000026,$$

và

$$1\cdot10^9+2\cdot(-1)+3\cdot4+4\cdot1+5\cdot0 =1000000014.$$

Vì vậy năm dòng kết quả lần lượt là các giá trị đã cho trong Output.

Ví dụ 2

Input

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

Output

-1

Giải thích

Ba cạnh

$$3\rightarrow4,\qquad 4\rightarrow5,\qquad 5\rightarrow3$$

với các trọng số lần lượt là $-3$, $3$ và $-2$ tạo thành một chu trình có tổng trọng số

$$-3+3-2=-2<0.$$

Do đồ thị chứa chu trình âm nên kết quả duy nhất cần in là -1.