城市
时间限制：20s 空间限制：256MB
题目描述
A国是一个拥有n个城市的国家，其中城市s是A国的首都。
A国还有m条道路，每条道路连着两个不同的城市，但是一对城市间可能有多条道路。每一条道路都有它的长度，一条道路的通行时间与一条道路的长度成正比。
你作为A国的统治者，设计出了一种统计城市重要程度的方法：
1、一条道路的重要度为：在这条道路不能使用的情况下，到首都s的最短时间会变长的城市的数目。
2、一个城市的重要度为：以它作为一端的所有道路的重要度的和。
现在，你知道了A国的道路连接情况，你需要计算出每一个城市的重要度。
输入格式
第一行，两个整数n,m，表示有A国有n个城市及m条道路。
第2~m+1行，每行三个整数u,v,l，描述了一条道路的两个端点城市及长度。
第m+2行，一个整数s，表示A国首都的编号
输出格式
n行，每行一个整数，第i行为编号i的城市的重要度。
样例输入
4 4 1 2 3 2 3 4 3 4 5 4 1 2 1
样例输出
2 1 0 1
提示
100%的数据，1<=n<=100000，1<=m<=200000，1<=l<=10^8
题目来源
没有写明来源