Problem I: 单源最短路径（困难版）

这里有一张 n 个点 m 条边的有向无负权图，对于题目给定的起点，求出从这个起点出发到其他所有节点的最短路径。（困难版与简单版相比只有数据范围不同）

第 1 行有三个正整数 n(2 <= n <= 100000), m(2 <= m <= 200000), k(1 <= k <= n)，表示这张图有 n 个点、m 条边，以及起点 k;

第 2 行到第 m+1 行每行有三个正整数 x, y(1 <= x, y <= n), v(0 <= v <= 10000), 表示有一条从 x 到 y 的边，这条边的权值是 v;

保证这张图上没有重边和自环。

输出 n 行，其中第 i 行输出起点到第 i 个点的最短路径，如果不存在路径则输出 -1

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