Trước kia, Tùng và Bách là hai bạn cùng lớp. Còn bây giờ hai bạn học khác trường nhau. Cứ mỗi sáng, đúng \(6\) giờ, cả hai đều đi từ nhà tới trường của mình theo con đường mất ít thời gian nhất (có thể có nhiều con đường đi mất thời gian bằng nhau và đều ít nhất). Nhưng hôm nay, hai bạn muốn gặp gỡ nhau để bàn việc họp lớp cũ nhân ngày 20-11.

Cho biết, sơ đồ giao thông của thành phố gồm \(N\) nút giao thông được đánh số từ \(1\) đến \(N\) và \(M\) tuyến đường phố (mỗi đường phố nối hai nút giao thông). Vị trí nhà của Tùng và Bách cũng như trường của hai bạn đều nằm ở các nút giao thông. Cần xác định xem Tùng và Bách có cách nào đi thoả mãn yêu cầu nêu ở trên, đồng thời họ lại có thể gặp nhau ở nút giao thông nào đó trên con đường tới trường hay không ? (Ta nói Tùng và Bách có thể gặp nhau tại một nút giao thông nào đó nếu họ đến nút giao thông này tại cùng một thời điểm). Nếu có nhiều phương án thì hãy chỉ ra phương án để Tùng và Bách gặp nhau sớm nhất.

Input

• Dòng đầu tiên chứa \(2\) số nguyên dương \(N,\ M\ (1\leq N\leq100)\);
• Dòng tiếp theo chứa 4 số nguyên dương \(Ha,\ Sa,\ Hb,\ Sb\) lần lượt là số hiệu các nút giao thông tương ứng với: nhà Tùng, trường của Tùng, nhà Bách, trường của Bách.
• Dòng thứ \(i\) trong số \(M\) dòng tiếp theo chứa \(3\) số nguyên dương \(A,\ B,\ T\). Trong đó, \(A\) và \(B\) là hai đầu của tuyến đường phố \(i\). Còn \(T\) là thời gian (tính bằng phút) cần thiết để Tùng (hoặc Bách) đi từ \(A\) đến \(B\) cũng như từ \(B\) đến \(A\).

Giả thiết là sơ đồ giao thông trong thành phố đảm bảo để có thể đi từ một nút giao thông bất kỳ đến tất cả các nút còn lại.

Output

• Dòng \(1\): Ghi từ YES hoặc NO tuỳ theo có phương án giúp cho hai bạn gặp nhau hay không.

Trong trường hợp có phương án thì ghi:

• Dòng \(2\): Ghi thời gian ít nhất để Tùng tới trường;
• Dòng \(3\): Ghi các nút giao thông theo thứ tự Tùng đi qua;
• Dòng \(4\): Ghi thời gian ít nhất để Bách tới trường;
• Dòng \(5\): Ghi các nút giao thông theo thứ tự Bách đi qua;
• Dòng \(6\): Ghi số hiệu nút giao thông mà hai bạn gặp nhau;
• Dòng \(7\): Thời gian sớm nhất tính bằng phút kể từ \(6\) giờ sáng mà hai bạn có thể gặp nhau.

Ví dụ

Sample input

6 7
1 6 2 5
1 3 10
1 4 10
2 3 5
3 4 5
3 6 15
4 5 20
4 6 15

Sample output

YES
25
1 4 6
30
2 3 4 5
4
10

Note

Sơ đồ giao thông sau với \(N=6,\ M=7,\ Ha=1,\ Sa=6,\ Hb=2,\ Sb=5\):