Trò chơi hái hoa (trochoihh.*)

Trong đợt trại hè Tin học miền trung diễn ra tại thành phố ĐNN, ban tổ chức đã tổ chức cho các đoàn trò chơi hái hoa như sau: Có \(k\ (1 \leq k \leq 10)\) loại hoa (các loại hoa được đánh chỉ số từ 1 đến \(k\)) được ban tổ chức sắp xếp tại \(n\ (1 < n \leq 1000)\) vị trí (các vị trí được đánh chỉ số từ 1 đến \(n\)). Có \(m\ (1 \leq m \leq 30000)\) đoạn đường 2 chiều nối giữa các vị trí với nhau đảm bảo luôn có đường đi giữa hai vị trí bất kì, thời gian đi lại trên đoạn đường nối giữa hai vị trí \(x\) và \(y\ (1 \leq x,y \leq n)\) là \(t\ (1 \leq t \leq 10000)\ \). Nhiệm vụ của mỗi đội là xuất phát từ vị trí 1 di chuyển đến đích là vị trí \(n\) sao cho hái được đủ \(k\) loại hoa và thời gian về đích là ít nhất. Vì mỗi đội có 2 người chơi nên hoa của mỗi đội là số hoa của cả 2 người gộp lại và thời gian về đích là thời gian lớn nhất của 2 người trong đội. Mỗi người trong đội có thể chọn một hành trình bất kì, có thể đi các đoạn đường giống nhau và mỗi vị trí có thể đến nhiều lần.

Yêu cầu: Xác định thời gian ít nhất của đội giành chiến thắng.

Dữ liệu vào:

+ Dòng đầu ghi 3 số nguyên \(n,\ m,\ k\);

+ Trong \(n\) dòng tiếp theo, dòng thứ \(i\) ghi thông tin về các loại hoa được bố trí tại ví trí thứ \(i\ (1 \leq i \leq n)\); số đầu tiên ghi số nguyên \(c\ (0 \leq c \leq k)\) là số lượng các loại hoa, \(c\) số tiếp theo là chỉ số các loại hoa ở vị trí đó.

+ Trong \(m\) dòng cuối, mỗi dòng ghi thông tin về một đoạn đường gồm 3 số lần lượt là \(x,\ y,\ t\).

Các số trong tệp cách nhau ít nhất một dấu cách.

Kết quả: Ghi một số duy nhất là thời gian ít nhất tìm được.

Ví dụ:

Input	Output
5 5 5 1 1 1 2 1 3 1 4 1 5 1 2 10 1 3 10 2 4 10 3 5 10 4 5 10	30

Ràng buộc:

+ Có 20% số test tương ứng 20% số điểm có \(k = 1\);

+ Có 30% số test tương ứng 30% số điểm có \(k = 2\);

+ Có 50% số test thương ứng 50% số điểm có \(3 \leq k \leq 10\).