3222. [SYOI 2019][東方S#]河童与灵力

【题目描述】

在幻想乡妖怪之山，有一个叫做河城荷取的河童，她喜爱创造，但创造的同时她又需要大量的灵力来维持自己的消耗。与此同时，在幻想乡有着N座神社，每座神社中所供奉的神明会为信徒提供一定量的灵力，神社之间由M条人间之里的道路组成。由于不同神社中供奉的神明不同，因此所产出的灵力也有所不同，人间之里的道路也只能供灵力进行单向传递。

尽管如此，仍然有部分神社之间的灵力可以互相传递，我们则称这种神社与人间之里的道路的集合为【れいりょくかいろう】。

现在河城荷取制造了一些灵力汲取器，每个汲取器可以同时汲取一座神社或一个【れいりょくかいろう】中产生的所有灵力。请告诉河城荷取至少需要多少个灵力汲取器才能保证吸收幻想乡神社产生的所有灵力。

由于河城荷取需要亲自去每个汲取器处收取灵力，而人间之里的道路又是单向的，因此河城荷取可以在必要时刻消耗部分灵力打开灵力通路以便逆行道路。河城荷取一定会由她自己所在的神社出发，并且河城荷取每一次行动中只能取回一个汲取器中的灵力，拿到灵力后河城荷取就可以直接带着灵力传送回到自己的神社（传送不消耗灵力）。请求出河城荷取在取回所有可以取到的灵力后灵力增加的最大值。

说明：河城荷取作为妖怪之山中的神明，自身灵力无穷大（因此不会出现没灵力开路的情况）

【输入格式】

第一行三个正整数表示神社个数N，道路条数M，河城荷取所在神社S，下面M行每行三个正整数表示道路起点，终点，逆行花费，最后N行表示每个神社中灵力数量

【输出格式】

两个正整数，代表河城荷取所需灵力汲取器的个数和河城荷取在取回所有可以取回的灵力后灵力增加量的最大值

【样例输入】

5 5 2
4 3 493986
2 1 163676
3 2 22690
5 1 331841
5 2 475416
55071
286190
295774
14405
477679

【样例输出】

5  257912

【提示】

N,M<=50000

【来源】

TOJO LINE 的水题欢乐赛T1