Một thành phố có địa điểm được đánh số từ đến , có đoạn đường hai chiều, đoạn đường thứ nối hai địa điểm với độ dài .
Nhóm bạn thân của Nam có người đều sống trong thành phố, Nam được đánh chỉ số và các bạn của Nam được đánh chỉ số lần lượt từ đến . Ngày chủ nhật tới được nghỉ học, mỗi bạn trong nhóm sẽ chạy bộ đến công viên ưa thích của mỗi người để tập thê dục. Người thứ có nhà nằm ở địa điểm ) và chủ nhật sẽ tập thể dục ở công viên ưa thích nằm ở địa điểm . Đề tiết kiệm thời gian, mỗi người sẽ xuất phát từ nhà đi tới công viên theo một đường đi có độ dài ngắn nhất.
Một đường đi gồm địa điểm xuất phát từ địa điểm và kết thúc tại địa điểm là một chuỗi liên tiếp các địa điểm: sao cho có đoạn đường nối trực tiếp giữa hai địa điểm liên tiếp và trong chuỗi. Độ
dài của một đường đi là tổng độ dài của các đoạn đường nối trực tiếp hai địa điểm liên tiếp trên đường đi đó.
Để việc tập thể dục trở nên vui vẻ hơn, Nam mong muốn có thể được đi chung với các bạn thân của mình trên đường đi tập thể dục. Nam được gọi là đi chung với một người bạn trên đoạn đường nối trực tiếp hai địa điểm và khi và chỉ khi đoạn đường này đều nằm trên đường đi tập thể dục của hai người và cả hai người đều đi đến địa điểm tại cùng một thời điểm trước khi cùng nhau đi đến địa điểm . Gọi là tổng độ dài của các đoạn đường mà Nam đi chung với ít nhất một người bạn thân của mình. Nam muốn giá trị của là càng lớn càng tốt.
Chủ nhật, theo dự định, mỗi người đều sẽ xuất phát đi tập thể dục vào lúc giờ sáng. Để có thể đạt được là lớn nhất, Nam cố găng thuyết phục mỗi người bạn thân của mình đi theo một đường đi ngắn nhất và xuất phát tại một thời điểm nào đó theo kế hoạch của Nam. Do đi theo đường đi có độ
đài ngắn nhất nào cũng không làm thay đổi khoảng thời gian di chuyển trên đương nên tất cả đều đồng ý đi theo các lộ trình đường đi ngắn nhất mà Nam đề xuất. Tuy nhiên, việc thay đổi giờ xuất phát, trước hoặc sau giờ sáng, có thể làm ảnh hưởng tới các kế hoạch cá nhân khác nên Nam chỉ thuyết phục được việc thay đổi thời gian xuất phát đối với những ai dễ tính mà thôi. Do đã quen với việc thức dậy sớm và xuất phát lúc giờ sáng, Nam không thay đổi thời điểm xuất phát của mình.
Yêu cầu: Biết rằng để đi một đơn vị khoảng cách mất một đơn vị thời gian, biết danh sách những bạn dễ tính, hãy giúp Nam lên kế hoạch để đạt được lớn nhất.
Dữ liệu vào:
Dòng đầu tiên chứa ba số nguyên và ;
Dòng thứ trong số dòng tiếp theo chứa ba số nguyên mô tả đoạn đường hai chiều nối hai địa điểm và với độ dài . Dữ liệu đảm bảo luôn tồn tại đường đi giữa hai địa điểm bất kì và không có hai đoạn đường nào nối trực tiếp cùng một cặp địa điểm;
Dòng tiếp theo chứa hai số nguyên và tương ứng là địa điểm xuất phát và địa điểm kết thúc đường đi tập của Nam;
Dòng thứ trong số dòng tiếp theo, , chứa ba số nguyên tương ứng là độ khó/dễ tính, địa điểm xuất phát và địa điểm kết thúc đường đi tập của người bạn có chỉ số , trong đó bằng nghĩa là khó tính và bằng nếu đễ tính.
Các số trên cùng một dòng cách nhau bởi dấu cách.
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là giá trị lớn nhất của .
