Giải bài trực tuyến

Kì thi lập trình sinh viên ACM-ICPC kết thúc cũng là lúc ktuan và microsoft trở về Việt Nam ăn Noel. Sau khi gói gém xong đồ đạc, cả hai đồng ý với nhau sẽ đi MRT (Mass Rapid Transit, hệ thống xe điện ở Singapore) từ NTU ra sân bay Changi. Hai bạn quyết định mang đi một số đồng xu để trả tiền MRT, các đồng xu gồm nhiều mệnh giá khác nhau, mỗi mệnh giá bao gồm 1 số lượng đồng xu nhất định và thỏa mãn điều kiện:

• Mỗi đồng xu có mệnh giá là một số nguyên dương
• Tổng giá trị của tất cả các đồng xu là S
• Mọi số tiền trong đoạn 1 -> S đều chỉ có duy nhất một cách dùng các đồng xu mang theo để trả. Ví dụ với S = 5, những cách mang tiền đi là (1, 2, 2), (1, 1, 1, 1, 1) và (1, 1, 3). Những cách mang tiền không đúng ý của hai bạn là : (1, 1, 1, 2) vì số tiền 2 có thể trả bằng (1, 1) hoặc (2) ; số tiền 3 cũng có thể trả bằng (1, 1, 1) và (1, 2).

Trên đường đi hai bạn phải đi qua một số trạm (NTU và sân bay Changi cũng là trạm MRT), và để đi từ trạm này đến trạm khác hai bạn sẽ phải trả phí. Tuy nhiên cách thức thu phí ở Singapore cũng khá lạ đời. Nếu có chuyến MRT từ trạm X đến trạm Y thì phí của chuyến này là F_XY, tuy nhiên bạn không cần phải trả số tiền F_XY mà phải chọn một loại mệnh giá xu bạn đang có trên tay sao cho còn lại đúng F_XY đồng xu mệnh giá này và trả hết số xu mệnh giá đó.

Yêu cầu: Không cho biết các mệnh giá xu và số lượng xu mang đi, hãy giúp hai bạn chọn các đồng xu thỏa mãn điều kiện ở trên và hai bạn có thể dùng các đồng xu này để có thể ra sân bay mà đi qua ít trạm MRT nhất. Hai bạn không muốn mang xu lên máy bay nên họ muốn sử dụng hết số xu mang đi.

Dữ liệu

• Dòng đầu tiên gồm 5 số tự nhiên N, M, NTU, CHANGI và S. Với N là số trạm MRT, M là số chuyến MRT giữa các trạm, NTU là chỉ số của NTU, CHANGI là chỉ số của sân bay Changi và S là tổng giá trị của số tiền hai bạn muốn mang đi.
• M dòng tiếp theo, mỗi dòng gồm 3 số tự nhiên X, Y và F_XY. Có nghĩa là có chuyến MRT từ trạm X đến trạm Y, và tất cả số đồng xu cùng loại phải trả trên chuyến này là F_XY.

Kết quả

• Ghi ra một số duy nhất là số trạm MRT ít nhất các bạn cần phải đi qua để đi từ NTU đến sân bay hoặc -1 nếu không có cách nào cho hai bạn ra sân bay được với những yêu cầu oái oăm về xu của họ.

Giới hạn

• 2 ≤ N ≤ 1000, 1 ≤ M ≤ 10000, 1 ≤ NTU, CHANGI ≤ N và NTU ≠ CHANGI
• 1 ≤ S ≤ 10⁹
• 0 ≤ F_XY ≤S với X ≠ Y

Ví dụ

Dữ liệu
4 5 1 4 5
1 2 1
1 3 2
2 4 2
3 4 1
1 4 5	

Kết quả
2

Giải thích

Có 3 cách mang xu thỏa mãn yêu cầu của hai bạn là : Cách 1 (5 đồng 1 xu) sẽ giúp hai bạn đi thẳng từ 1->4. Cách 2 (1 đồng 1 xu, 2 đồng 2 xu) và cách 3 (2 đồng 1 xu và 1 đồng 3 xu) sẽ giúp hai bạn đi đường 1->2->4 hoặc 1->3->4. Đường đi ngắn nhất mà sử dụng hết xu là 1->4.

Hạn chế

• Có 50% số test thỏa mãn N ≤ 100.