#1160. 城市

城市

Description

A国是一个拥有n个城市的国家,其中城市s是A国的首都。

A国还有m条道路,每条道路连着两个不同的城市,但是一对城市间可能有多条道路。每一条道路都有它的长度,一条道路的通行时间与一条道路的长度成正比。

你作为A国的统治者,设计出了一种统计城市重要程度的方法:

1、一条道路的重要度为:在这条道路不能使用的情况下,到首都s的最短时间会变长的城市的数目。

2、一个城市的重要度为:以它作为一端的所有道路的重要度的和。

现在,你知道了A国的道路连接情况,你需要计算出每一个城市的重要度。

Format

Input

第一行,两个整数n,m,表示有A国有n个城市及m条道路。

第2~m+1行,每行三个整数u,v,l,描述了一条道路的两个端点城市及长度。

第m+2行,一个整数s,表示A国首都的编号

Output

n行,每行一个整数,第i行为编号i的城市的重要度。

Samples

4 4
1 2 3
2 3 4
3 4 5
4 1 2
1
2
1
0
1

Limitation

100%的数据,1<=n<=100000,1<=m<=200000,1<=l<=10^8