题目描述
给定 N 个点和M 条单向道路，每条道路都连接着两个点，每个点都有自己编号，分别为 1∼N 。
问你从 S 点出发，到达每个点的最短路径为多少。
输入
输入第一行包含三个正整数 N,M,S。
第 2 到 M+1 行每行包含三个正整数 u,v,w，表示 u→v 之间存在一条距离为w 的路。
1≤N≤5×103 ，1≤M≤5×104 ，1≤ui ,vi ≤N，0≤wi ≤109 。
输出
输出仅一行，共N 个数，分别表示从编号S 到编号为 1∼N 点的最短距离，两两之间用空格隔开。（如果无法到达则输出−1）