Trong một căn phòng mờ tối, vào khoảng 23 giờ 55 phút, Milan ngồi xuống bên chiếc bàn ba chân và bắt đầu suy nghĩ về những hậu quả có thể xảy ra nếu một thảm họa hạt nhân xảy ra trong thành phố của mình. Vì Milan đang giữ vai trò thị trưởng, anh ấy rất am hiểu về tất cả các sự kiện liên quan.

Cụ thể, anh ấy biết rằng trong thành phố của mình có đúng $N$ người sinh sống và mỗi cư dân đều sống trong ngôi nhà riêng của họ. Giữa đúng $M$ cặp ngôi nhà có các con đường, và đối với mỗi con đường, thời gian cần thiết để đi qua nó đều đã được biết trước. Cuối cùng, Milan biết được $K$ ngôi nhà nào có hầm trú ẩn hạt nhân và mỗi hầm trú ẩn có thể chứa bao nhiêu người. Với tất cả những điều đó, Milan đang trăn trở với câu hỏi sau: "Thời gian tối thiểu cần thiết để sơ tán tất cả cư dân của thành phố này là bao nhiêu?" Hãy giúp Milan trả lời câu hỏi này.

Tất nhiên, việc sơ tán đòi hỏi mỗi cư dân phải đến được một hầm trú ẩn hạt nhân nào đó. Bạn có thể giả định rằng các cư dân di chuyển một cách tối ưu (theo đường ngắn nhất) và nhiều người có thể di chuyển đồng thời dọc theo một con đường theo các hướng khác nhau. Ngoài ra, bạn có thể giả định rằng tồn tại ít nhất một con đường giữa hai ngôi nhà bất kỳ bằng cách sử dụng một tập hợp con các con đường đã cho.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên dương $N$ ($1 \le N \le 100\,000$), $M$ ($1 \le M \le 300\,000$) và $K$ ($1 \le K \le 17$), lần lượt đại diện cho số lượng cư dân, số lượng con đường và số lượng hầm trú ẩn hạt nhân. Các ngôi nhà được đánh số từ $1$ đến $N$.

Trong mỗi dòng tiếp theo trong số $M$ dòng là ba số nguyên dương $A, B$ ($1 \le A, B \le N, A \neq B$) và $C$ ($1 \le C \le 10^9$), biểu thị rằng giữa các ngôi nhà được đánh số $A$ và $B$ có một con đường cần $C$ đơn vị thời gian để đi qua.

Trong mỗi dòng tiếp theo trong số $K$ dòng là hai số nguyên dương $X$ ($1 \le X \le N$) và $Y$ ($1 \le Y \le 10^9$), biểu thị rằng tại ngôi nhà số $X$ có một hầm trú ẩn hạt nhân có thể chứa tối đa $Y$ người. Tổng sức chứa của tất cả các hầm trú ẩn sẽ lớn hơn hoặc bằng $N$.

Dữ liệu ra

In ra một dòng duy nhất là thời gian tối thiểu cần thiết để sơ tán tất cả cư dân của thành phố này.

Nhiệm vụ con

Ví dụ

Dữ liệu vào 1

5 5 2 
1 2 1 
1 3 3 
2 3 4 
3 4 1 
4 5 1 
1 10 
4 2

Dữ liệu ra 1

3

Ghi chú 1

Trong 3 đơn vị thời gian, những người từ các ngôi nhà số 1, 2 và 3 có thể đi đến hầm trú ẩn tại ngôi nhà số 1, và những người từ các ngôi nhà số 4 và 5 có thể đi đến hầm trú ẩn tại ngôi nhà số 4. Trong thời gian ngắn hơn, không phải tất cả mọi người đều có thể đến được hầm trú ẩn vì hầm trú ẩn tại ngôi nhà số 4 chỉ chứa tối đa hai người.

Dữ liệu vào 2

7 8 3 
1 2 5 
2 3 3 
3 4 5 
1 4 1 
4 5 7 
5 6 2 
6 7 1 
4 7 4 
3 3 
7 3 
6 2

Dữ liệu ra 2

5