堆优化单源距离

难度：T2

【知识点：堆优化Dijkstra】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

给出有向带权图和源点 $s$。边只能沿给定方向通行，路径长度是经过边的权值之和。求从 $s$ 到每个顶点的最短距离；$s$ 到自身的距离为 $0$。

输入格式

输入$n$、$m$、$s$，随后$m$行有向边$u$、$v$、$w$；允许重边和自环。

输出格式

按编号输出全部距离；不可达输出-$1$。

数据范围

$1\le n\le 100000$，$0\le m\le 200000$，$0\le w\le 10^9$。

样例输入

3 3 1
1 3 10
1 2 2
2 3 3

样例输出

0 2 5

样例说明

源点 $1$ 到自身的距离为 $0$，到 $2$ 的距离为 $2$；到 $3$ 经过 $2$ 的距离为 $2+3=5$，比直接走的 $10$ 更短。