BELLMAN-FORD

Cho đồ thị G=(V, E, W) gồm N đỉnh, các đỉnh được đánh số từ 1 đến N,  và 2 đỉnh s, t thuộc V.
Tìm đường đi ngắn nhất từ s đến t.

Dữ liệu vào: từ tệp văn bản BELLMAN.INP

+ Dòng đầu tiên ghi 4 số nguyên n, m, s, t lần lượt là số đỉnh, số cung, đỉnh xuất phát và đỉnh đích

+ m dòng tiếp theo mỗi dòng gồm 3 số u, v, w cho biết w (w≠0) là trọng số của cung (u,v).

Dữ liệu ra: Ghi vào tệp văn bản BELLMAN.OUT

+ Dòng đầu ghi một số nguyên cho biết độ dài đường đi ngắn nhất từ s đến t, nếu không có đường đi ngắn nhất thì ghi ‘NO’.

+ Nếu dòng đầu ghi một số nguyên thì dòng thứ 2 ghi một đường đi ngắn nhất từ s đến t.

Ví dụ:

BELLMAN.INP	BELLMAN.OUT
6 7 1 4 1 2 1 1 6 10 2 3 2 3 4 20 3 6 3 5 4 5 6 5 4	15 1 2 3 6 5 4

Giới hạn:

+ N<=2000_; M<=20000_; |w|<=20000     

TEST