Đường đi ngắn nhất thứ K

Cho một đồ thị vô hướng, có trọng số, liên thông gồm $n$ đỉnh và $m$ cạnh.

Gọi $d_{i,j}$ là độ dài đường đi ngắn nhất giữa đỉnh $i$ và đỉnh $j$. Xét mảng gồm tất cả các giá trị $d_{i,j}$ với $1\le i<j\le n$, tức là đường đi từ một đỉnh tới chính nó không được tính, và hai đường đi $i\to j$ và $j\to i$ chỉ được tính một lần. Mảng này có đúng $\frac{n(n-1)}{2}$ phần tử.

Hãy sắp xếp mảng đó theo thứ tự không giảm và in ra phần tử thứ $k$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$: số đỉnh, số cạnh và thứ hạng cần tìm.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $x$, $y$, $w$: một cạnh nối hai đỉnh $x$ và $y$ với trọng số $w$.

Dữ liệu ra

Một số nguyên duy nhất: độ dài đường đi ngắn nhất đứng thứ $k$ theo thứ tự không giảm.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $n-1\le m\le min(\frac{n(n-1)}{2},2·{10}^5)$
• $1\le k\le min(\frac{n(n-1)}{2},400)$
• $1\le x,y\le n$, $x\ne y$, $1\le w\le {10}^9$
• Đồ thị liên thông, không có khuyên và không có cạnh song song (giữa mỗi cặp đỉnh có nhiều nhất một cạnh).

Ví dụ