#P4227. 城市
城市
城市
题目描述
A 国有 座城市。城市 是首都。给定 条连接不同城市的双向道路,每条道路有一个正整数长度。同一对城市可由多条道路连接。
单独封闭一条道路以后,原来能到达首都的城市中,到首都的最短路变长或变得无法到达的城市数量,就是这条道路的重要度。每条道路都在其他道路全部开放的情况下单独考察。
一个城市的重要度是与它直接相连的所有道路的重要度之和。求每座城市的重要度。
输入格式
第一行两个整数 ,分别为城市数和道路数。
接下来 行,每行三个整数 ,表示一条连接城市 和 、长度为 的道路。
最后一行一个整数 ,表示首都编号。城市编号为 至 。
输出格式
输出 行,第 行一个整数,表示城市 的重要度。
样例 #1
样例输入 #1
4 4
1 2 3
2 3 4
3 4 5
4 1 2
1
样例输出 #1
2
1
0
1
数据规模与约定
,,。