Cho một đồ thị vô hướng, có trọng số gồm \(n\) đỉnh và \(m\) cạnh. Tìm \(k\) đường đi ngắn nhất từ \(1\) đến \(n\).

Input

• Dòng đầu tiên gồm \(3\) số nguyên \(n,m,k\).
• \(m\) dòng tiếp theo, mỗi dòng gồm \(3\) số nguyên \(u,v,w\), có cạnh trọng số \(w\) nối \(u,v\).

Output

• In ra \(k\) chi phí đường đi ngắn nhất (theo thứ tự tăng dần)

Điều kiện

• \(1 \le n \le 10^5\)
• \(1 \le m \le 2 \times 10^5\)
• \(1 \le u,v \le n\)
• \(1 \le w \le 10^9\)
• \(1 \le k \le 10\)

Sample Input 1

4 6 3
1 2 1
1 3 3
2 3 2
2 4 6
3 2 8
3 4 1

Sample Output 1

4 4 7

Giải thích: Đường bay 1 -> 3 -> 4 (chi phí 4), 1 -> 2 -> 3 -> 4 (chi phí 4) và 1 -> 2 -> 4 (chi phí 7).