Bác John vừa tổ chức một đội đua tiếp sức bằng cách chọn ra con bò của bác. Cuộc đua diễn ra trên nông trang của bác nơi có cánh đồng đươc đánh số và đường đi hai chiều có tính chất duy nhất để nối các cặp hai cánh đồng riêng biệt. Bạn sẽ được cho thời gian mỗi con bò cần có để đi qua mỗi đoạn đường.
Con bò đầu tiên bắt đầu cuộc đua tại cánh đồng và chạy tới đích tại cánh đồng nhanh nhất có thể. Khi con bò đầu tiên kết thúc, con bò tiếp theo sẽ bắt đầu từ cánh đồng và chạy tới cánh đồng và cứ thế đến con bò thứ . Trong cuộc đua này, không có hai con bò nào có thể theo chính xác cùng một hành trình (một hành trình là một dãy các cánh đồng).
Viết chương trình để tính thời gian cần thiết nhỏ nhất có thể được cho đội đua tiếp sức của bác John. Bạn được đảm bảo rằng tồn tại thời gian nhỏ nhất có thể. Mọi con bò có thể đi lại một đường nối trong hành trình của mình tới chuồng khác nếu nó là cần thiết cho một lời giải “tối ưu”. Ngay khi một con bò tới cánh đồng , lượt đua của nó xem như kết thúc.
Dữ liệu vào:
Dòng đầu tiên ghi ba số nguyên và ;
dòng tiếp theo mỗi dòng chứa ba số nguyên mô tả một đường đi trực tiếp nối cánh đồng đầu, cành đồng cuối và thời gian nguyên để đi qua đường nối (trong khoảng ).
Dữ liệu ra:
Gồm duy nhất một số nguyên chỉ giá trị nhỏ nhất tìm được.
Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.
