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

• 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) ~.

Kết quả

• 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 ~.

Ràng buộc

• ~ n≤2000 ~;
• ~ m≤20000 ~;
• ~|w|≤20000 ~;

Ví dụ:

Input 1

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 

Output 1

15
1 2 3 6 5 4