时间限制：1秒　　内存限制：256M

---

【题目描述】

　　对于 \(n\) 个点，\(m\) 条边带权无向图 \(G\)，请计算从起点 \(s\) 到各点经过的边数不超过 \(k\) 的最短路径长度。

【输入格式】

　　第一行为 \(n,m,s,k\)，接下来的 \(m\) 行，每行表示一条边：\(a,b,w\)。

【输出格式】

　　共 \(n\) 行，第 \(i\) 行表示 s 到 \(i\) 的最短距离，如果不存在最短路，输出inf。

【输入输出样例】

　Input

5 6 1 2
1 2 1
2 3 2
1 3 4
4 1 6
3 4 1
4 5 3

　Output

0
1
3
5
9

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤10000\)，\(1≤m≤10000\)，\(1≤k≤20\)，\(1≤w≤50000\)。

【来源】

　　Mr.he