Mạng lưới giao thông thành phố gồm \(n\) nút được đánh số từ 1 đến \(n\) và \(m\) đường một chiều nối giữa các cặp nút. Để giảm được độ dài của đường đi ngắn nhất giữa hai nút trọng yếu \(s\) và \(t\) khác nhau, một danh sách gồm \(k\) đường hai chiều được đề xuất để xem xét xây dựng

Nhiệm vụ của bạn là chọn 1 đường hai chiều trong danh sách đề xuất trên để xây dựng sao cho độ dài đường đi giữa \(s\) và \(t\) là nhỏ nhất

Dữ liệu vào:

+ Dòng đầu tiên chứa 5 số nguyên dương: \(n\) \((n \leq 1000)\), \(m\), \(k\) \((k \leq 300)\), \(s\) \((1 \leq s \leq n)\), \(t\ (1 \leq t \leq n)\) cách nhau bởi dấu cách.

+ Dòng thứ i trong \(m\) dòng tiếp theo chứa 3 số nguyên dương \(d_{i},\ c_{i},\ l_{i}\) cách nhau bởi dấu cách, trong đó \(l_{i}\) là độ dài \((0 \leq l_{i} \leq 1000)\) của đường một chiều thứ \(i\) từ nút \(d_{i}\) đến nút \(c_{i}\).

+ Dòng thứ \(j\) trong \(k\) dòng tiếp theo chứa 3 số nguyên dương \(u_{j}\), \(v_{j}\) và \(q_{j}\) \((q_{j} \leq 1000)\) cách nhau bởi dấu cách, trong đó \(q_{j}\) là độ dài đường đi hai chiều được đề xuất thứ \(j\) nối hai nút \(u_{j}\) và \(v_{j}\).

Dữ liệu ra: Ghi một số nguyên duy nhất là độ dài nhỏ nhất có thể của đường đi ngắn nhất của hai nút trọng yếu sau khi xây dựng xong một đường hai chiều từ danh sách đề xuất. Trường hợp không có đường đi từ \(s\) đến \(t\) ghi \(- 1\)

(Không nhất thiết phải có đường 2 chiều trong đường đi ngắn nhất)

Ví dụ: