小明的爷爷即将迎来 80 大寿，于是这一天一大家子人决定来给老寿星祝寿。

已知共有 n 家人分别住在城市的不同位置（位置编号 1~n ，包含小明爷爷家），他们分别可以开车通过一定时间沿特定道路到达另外几位亲戚家。但由于这一天城市交通拥堵，这些道路仅视为单向连通。

现在小明希望你帮忙规划路线，并确认每位亲戚往返小明爷爷家最少需要花费的时间。

第一行输入三个数 n,m,l，分别表示多少家、道路总数和小明爷爷家的位置。

之后 m 行，每行三个数 u,v,t ，表示这一天从位置 u 到位置 v 开车需要 t 时间到达。

其中 2\leq n \leq10^5 ，  2\leq m\leq 2\times 10^5 ，  1\leq t\leq10^6 。

输出 n 行，其中第 i 行表示住在位置 i 的亲戚往返的时间；对于小明爷爷家输出 0，如果无法往返则输出 impossible 。

对于样例中的情形，

位置 1 为小明爷爷家，往返时间为 0 ；

位置 2 到小明爷爷家通过 2-3-1 ，返回 1-2，往返时间 1+3+2=6 ；

位置 3 到小明爷爷家通过 3-1 ，返回 1-2-3，往返时间 3+2+1=6。