题目描述

n个城市，有m条单向道路连接起来。

骑自行车通过道路，需要耗费体力值；经过某些道路，可以补充体力。

请问从城市s到其他各个城市的分别至少耗费多少体力？各有多少种方案？

输入

第一行：n、m、s
接下来m行，每行3个数a、b、c，表示从城市a到城市b需要耗费c体力，c可以为负表示补充体力。

输出

输出n-1行，每行两个整数，分别表示起点s到其他城市的最少体力和方案数，按照城市编号从小到大输出。
保证结果在int范围；如果不能到达，该行输出两个0。

样例输入

4 5 2

1 2 3

2 3 1

2 3 2

3 4 5

3 4 5

样例输出

0 0

1 1

6 2
提示

1 <= n <= 10^4

1 <= m <= 2∗10^5

10个点n的数据范围：5, 20, 100, 300, 500, 1000, 3000, 5000, 8000, 10000, 10000

保证有解，结果在int范围内。

求助思路