A551.单源最短路径2

给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

第一行输入三个整数 $n,m,s$，分别表示点数、有向边数和出发点编号。

接下来 $m$ 行，每行输入三个整数 $u,v,w$，表示从 $u$ 到 $v$、长度为 $w$ 的有向边。

若存在负环输出 no solution，否则输出一行 $n$ 个整数，第 $i$ 个数表示 $s$ 到第 $i$ 个点的最短路径，若不能到达则输出 -1。

数据范围

$1\le n,m\le1000$，$1\le s,u,v\le n$，$-1000\le w\le1000$。