给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出点 s 到第 i 个点的最短路径，若不能到达则输出 -1。

第一行包含三个整数 n, m, s ，分别表示点的个数、有向边的个数、出发点的编号。

接下来 m 行每行包含三个整数 u, v, w ，表示一条 u \to v 的边，长度为 w 。

输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 -1。

• 1 \leq n \leq 1000
• 1 \leq m \leq 5 \times 10^5
• 1 \leq u, v \leq n
• w \geq 0
• \sum w < 2^{31}