# 【模板】单源最短路径

## 输出格式

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

0 2 4 3


## 数据范围及提示

$1 \le n \le 10^5$$1 \le m \le 2\times 10^5$$s=1$$1\le u_i,w_i \le n$$0\le w_i \le 10^9$

data updata by Macesuted and xlqs23