Hoàn thiện đồ thị

Cho một đồ thị vô hướng gồm $n$ đỉnh được đánh số từ $0$ đến $n-1$ và $m$ cạnh. Mỗi cạnh có một trọng số là số nguyên dương.

Một số trọng số đã bị xoá: các cạnh này được ghi trọng số bằng $0$. Bạn cần gán lại cho mỗi cạnh bị xoá một trọng số nguyên dương (không vượt quá ${10}^{18}$) sao cho độ dài đường đi ngắn nhất giữa hai đỉnh $s$ và $t$ trong đồ thị thu được đúng bằng $L$.

Các cạnh có trọng số khác $0$ phải giữ nguyên trọng số. Hãy xác định xem có cách gán như vậy hay không, và nếu có thì đưa ra một cách bất kỳ.

Giữa mỗi cặp đỉnh có nhiều nhất một cạnh.

Dữ liệu vào

• Dòng đầu chứa năm số nguyên $n$, $m$, $L$, $s$, $t$.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i$, $v_i$, $w_i$ mô tả một cạnh giữa đỉnh $u_i$ và $v_i$ có trọng số $w_i$. Nếu $w_i=0$ thì trọng số của cạnh này đã bị xoá.

Dữ liệu ra

Nếu không tồn tại cách gán thoả mãn, in ra một dòng duy nhất chứa NO.

Ngược lại, dòng đầu in ra YES. Tiếp theo in ra $m$ dòng mô tả các cạnh của đồ thị kết quả: mỗi dòng gồm ba số $u_i$, $v_i$, $w_i$. Tập cạnh phải trùng khớp với đồ thị ban đầu, các trọng số không bị xoá phải giữ nguyên, còn các trọng số mới là số nguyên dương không vượt quá ${10}^{18}$. Đường đi ngắn nhất giữa $s$ và $t$ phải có độ dài đúng bằng $L$.

Thứ tự các cạnh trong output không quan trọng. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

• $2\le n\le 1000$
• $1\le m\le 10000$
• $1\le L\le {10}^9$
• $0\le s,t\le n-1$, $s\ne t$
• $0\le u_i,v_i\le n-1$, $u_i\ne v_i$
• $0\le w_i\le {10}^9$

Ví dụ