题目描述

国内大多数高校都会有一个活动，叫做校园跑。校园跑是一种在校园内进行的跑步运动，旨在提高学生的身体素质和团队合作能力。校园跑的规则是，每个参与者都要从自己所在的建筑物出发，沿着校园内的道路跑步，每到一个建筑他们需要到达这个建筑物的必经点，这样他们的手机会自动记录一次该建筑物。每个参与者都要尽可能多地经过必经点，同时也要尽可能快地完成跑步。

每个参与者的成绩由两个指标决定：经过的必经点个数和跑步总时间。经过的必经点个数越多，跑步总时间越短，成绩越好。校园跑不仅可以锻炼身体，还可以增加对校园各个建筑物的了解和认同感。

塔子哥也参加了他的学校的这个活动，由很多个建筑物组成，每个建筑物都有一个编号，从1到 $n$ 。一个学生从某个建筑物开始，沿着校园中的道路跑步。

由于学社联为了丰富这个活动的内容，让这个活动变得更好玩，他们会在一些建筑物的必经点安排一些小游戏，到达必经点后需要完成这些小游戏才能继续进行跑步。

但是仅一个人把学校所有的建筑物都跑完并完成小游戏，又会过于疲惫，于是学社联允许参加的学生们进行组队，以用时最长的那个人的成绩作为最终成绩。

塔子哥和他的同学组成了一支小队（不限人数），他们想知道，从某个建筑物开始跑步，最多能经过多少个必经点，以及完成跑步的最快时间是多少。

我们已经知道了每个建筑物之间跑步的时间，以及每个必经点完成小游戏的时间，这些时间都用 $runTimes$ 列表给出了。

$runTimes[i]$ 表示从建筑物 $u$ 到 $v$ 建筑物的时间是 $runTime$ ，如果 $u$ 和 $v$ 相同，就表示是这个必经点需要玩小游戏的时间。那么，从 $u$ 到 $v$ 的时间就是两者相加。现在给定一个起始建筑物 $x$，请计算出完成跑步后能经过的最多必经点数和最终成绩时间。

输入描述

输入第一行为一个正整数 $n$ ，表示建筑物的个数.($1 \leq n \leq 100$)

输入第二行为一个正整数 $m$ ，表示路径的条数.($1 \leq m \leq 10^4$)

接下来 m 行输入每行为三个正整数 $u,v,runTime$，表示 $runTimes[i]$ 的三个元素，即从 u->v 需要的时间为 $runTime$,但不代表 v->u 也是如此.($1 \leq u,v,runTime \leq 100$)

最后一行输出校园跑的起点 $x$.($1 \leq x \leq n$)

输出描述

输出为2行。第一行输出为最终可经过的的必经点个数，第二行输出这些塔子哥小队全部完成跑步后的具体时间。

样例1

样例输入

5
9
1 2 3
1 3 4
2 4 6
2 5 7
5 5 5
4 4 4
3 3 3
2 2 2
1 1 1
1

样例输出

5
17

样例解释

​ 以建筑物1为起点计算小队最长耗时，分析可能会存在三条最大耗时路径,分别为1->3以及1->2->5以及1->2->4。

​ 第一条路径1->3路径下,总耗时为4(1->3耗时)+3(3自身耗时)=7。第二条路径1->2->5路径下,总耗时为3(1->2耗时)+2(2自身耗时)+7(2->5耗时)+5(5自身耗时)=17。第三条路径1->2->4路径下,总耗时为3(1->2耗时)+2(2自身耗时)+6(2->4耗时)+4(4自身耗时)=15。

​ 所以在此场景下，小队完成跑步的最短时间为38分钟，为可以经过的所有必经点的最长时间。

​ 最终输出结果分两行输出，最终12345五个必经点都可以经过，所以最终输出结果如样例1输出。

样例2

样例输入

5
6
1 2 10
1 3 20
2 4 30
3 4 40
4 5 50
5 1 60
3

样例输出

5
160