Đất nước C có thành phố lớn và con đường, mỗi con đường nối hai thành phố nào đó trong thành phố này. Giữa hai thành phố bất kỳ có tối đa một con đường nối trực tiếp. Trong con đường này, có một phần là đường một chiều, một phần là đường hai chiều. Đường hai chiều khi thống kê số lượng cũng được tính là 1 con đường.
Đất nước C lãnh thổ rộng lớn, sự phân bố tài nguyên ở mỗi nơi mỗi khác, dẫn đến việc giá của cùng một loại hàng hóa ở các thành phố khác nhau không nhất thiết giống nhau. Tuy nhiên, giá mua vào và giá bán ra của cùng một loại hàng hóa tại cùng một thành phố luôn giống nhau.
Thương nhân Along đến đất nước C du lịch. Khi biết thông tin giá hàng hóa có thể khác nhau ở các thành phố, anh ấy quyết định trong khi du lịch sẽ tận dụng chênh lệch giá hàng hóa giữa các thành phố để kiếm lại một ít chi phí đi lại. Giả sử thành phố của nước C được đánh số từ , Along quyết định xuất phát từ thành phố số , và cuối cùng kết thúc chuyến đi tại thành phố số . Trong quá trình du lịch, bất kỳ thành phố nào cũng có thể đi qua nhiều lần, nhưng không bắt buộc phải đi qua tất cả thành phố.
Along kiếm tiền lộ phí bằng cách giao thương như sau: Anh ấy sẽ chọn một thành phố đã đi qua để mua món hàng anh ấy thích nhất – quả cầu pha lê, và bán quả cầu này tại một thành phố khác mà anh ấy đi qua sau đó, dùng số tiền chênh lệch kiếm được làm lộ phí. Vì Along chủ yếu đến nước C để du lịch, anh ấy quyết định việc giao thương này chỉ thực hiện tối đa một lần. Tất nhiên, nếu không kiếm được chênh lệch giá thì anh ấy không cần thực hiện giao thương.
Giả sử nước C có 5 thành phố lớn, số hiệu thành phố và tình trạng kết nối đường đi như hình dưới, mũi tên đơn biểu thị đường một chiều, mũi tên đôi biểu thị đường hai chiều.
Giả sử giá quả cầu pha lê tại các thành phố lần lượt là .
Along có thể chọn lộ trình sau: , tại thành phố số mua quả cầu với giá , tại thành phố số bán quả cầu với giá , số tiền lộ phí kiếm được là .
Along cũng có thể chọn lộ trình sau: , tại lần thứ nhất đến thành phố mua quả cầu với giá , tại lần thứ hai đến thành phố bán quả cầu với giá , số tiền lộ phí kiếm được là .
Bây giờ cho biết giá quả cầu pha lê tại thành phố, thông tin về con đường (số hiệu hai thành phố mà mỗi con đường nối và tình trạng thông thương của con đường đó). Hãy cho Along biết, anh ấy có thể kiếm được tối đa bao nhiêu tiền lộ phí.
Dữ liệu:
Dòng đầu tiên chứa 2 số nguyên dương và , cách nhau bởi một dấu cách, lần lượt biểu thị số lượng thành phố và số lượng con đường.
Dòng thứ hai gồm số nguyên dương, mỗi hai số cách nhau một dấu cách, theo thứ tự biểu thị giá hàng hóa tại thành phố này.
dòng tiếp theo, mỗi dòng có 3 số nguyên dương , mỗi hai số cách nhau một dấu cách.
Nếu , biểu thị con đường này là đường một chiều từ thành phố đến thành phố .
Nếu , biểu thị con đường này là đường hai chiều giữa thành phố và thành phố .
Kết quả:
Xuất ra gồm 1 dòng, chứa 1 số nguyên, biểu thị số tiền lộ phí tối đa có thể kiếm được. Nếu không thực hiện giao thương, xuất ra .
Ví dụ:
Dữ liệu:
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
Kết quả:
5
Giới hạn:
Dữ liệu đảm bảo từ thành phố có thể đến được thành phố .
Với dữ liệu, ;
Với dữ liệu, ;
Với dữ liệu, không tồn tại lộ trình du lịch nào có thể xuất phát từ một thành phố và quay lại chính thành phố đó;
Với dữ liệu, , , , , giá quả cầu pha lê tại các thành phố .
