Cho một đồ thị vô hướng có trọng số gồm n đỉnh và m cạnh. Các đỉnh được đánh số từ 1 đến n.

Bạn hãy tìm đường đi ngắn thứ k trong đồ thị này (đường đi từ một đỉnh đến chính nó không được tính, đường đi từ đỉnh i đến j và từ j đến i được xem là một).

Cụ thể nếu d là ma trận đường đi ngắn nhất, ở đó d_ij là độ dài đường đi ngắn nhất giữa hai đỉnh i và j (1 ≤ i < j ≤ n), thì bạn cần đưa ra phần tử thứ k của mảng đã được sắp xếp gồm tất cả các d_ij (1 ≤ i < j ≤ n).

Dữ liệu vào:

+ Dòng đầu tiên chứa 3 số nguyên n, m và k (2 ≤ n, m ≤ 10⁵, 1 ≤ k ≤ 10³) lần lượt là số đỉnh, số cạnh của đồ thị và giá trị k.

+ Tiếp theo có m dòng, mỗi dòng chứa 3 số nguyên x, y và w (1 ≤ x, y ≤ n, 1 ≤ w ≤ 10⁹, x ≠ y) mô tả một cạnh nối hai đỉnh x, y với trọng số w (giữa hai đỉnh bất kỳ có tối đa một cạnh nối chúng).

Kết quả:

+ Một số nguyên là độ dài đường đi ngắn thứ k của đồ thị. Dữ liệu vào đảm bảo luôn tồn tại đường đi ngắn thứ k.

Ví dụ:

Ràng buộc:

+ Có 25% test: 1 ≤ k ≤ 3;

+ Có 25% test: n ≤ 10²;

+ Có 25% test: k ≤ 10²;

+ Có 25% còn lại: Như ràng buộc trong đề bài.