派蒙の问题(Easy Version)-Blog.Zheng

题目背景

你说得对，但是《原神》是由米哈游自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作“提瓦特”的幻想世界，在这里，被神选中的人将被授予“神之眼”，导引元素之力。你将扮演一位名为“旅行者”的神秘角色，在自由的旅行中邂逅性格各异、能力独特的同伴们，和他们一起击败强敌，找回失散的亲人——同时，逐步发掘“原神”的真相。

可爱的派蒙想把旅行者的光辉事迹发扬到宇宙中的其他星球上，所以她找到了你

题目描述

共有n 个星球,星球间有m 条可供飞船航行的双向航线，每条航线连接两星球a , b ，通过第i 条航线的所需时间为l。

派蒙想知道倘若她想要从起点星球x 开始，前往每个星球分别需要多少时间？(若无法到达，输出9223372036854776000)

输入格式

第一行三个整数n,m,s ；

接下来m 行，每行3 个整数a_i , b_i , l_i ；

输出格式

一行n 个整数，表示到每个星球的所需时间。

样例数据

样例输入

样例输出

0 2 4 3

数据范围

1 \le n \le 10^5 ;

1 \le m \le 2 \times 10^5 ;

1 \le a_i,b_i \le n ;

0 \le l_i \le 10^9 ;

0 \le \sum l_i \le 10^{18};