开开在思考一个局域网结构。考虑一个含有n个节点的网络，它们之间有m条双向有线电缆，被电缆连接的两个节点之间可以互相通信。当报文从一个节点通过电缆传送到另一个节点时，会产生时延。
在接入网络时，所有节点都没有自己的IP地址，在这里我们考虑一台DHCP服务器，其编号为k。节点在通信前需要向DHCP服务器申请IP地址。在申请IP时，该节点将向所有与之直接相连的节点发送广播报文，当一个节点接收到广播报文时会立即向与它直接相连的节点发送同样的报文。当DHCP服务器接受到该报文时，将产生广播应答报文。当起初的节点接收到该报文时，即可获得IP，同时向其目标节点发送报文。广播报文的发送不需要申请IP。你可以认为DHCP服务器也是一个普通的节点，可以传递报文，但不需要额外申请IP。电缆和节点都可以同时传输或处理多个报文。
现在，所有的节点同时申请IP，当所有的节点都申请到IP后，1号节点立即向n号节点发送一个报文。给你这一个网络拓扑结构，你需要帮助开开计算从1号节点向n号节点发送一个报文的最短时延。
输入格式:
第一行三个整数n,m,k，表示节点数量以及双向电缆数量，以及DHCP服务器编号。
接下来m行，每一行三个整数a_i,b_i,v_i，表示这一条电缆连接a_i,b_i两个节点，网络时延为1<=a_i,b_i<=n。
数据保证整个网络都是彼此可达的。
输出格式:
输出一行一个整数，表示最少的时延。
限制:
空间限制：128MByte
时间限制：1秒
样例:
输入：
5 7 3
1 2 2
2 4 4
1 3 3
3 4 2
2 3 2
1 4 1
4 5 3
输出：
14
提示:
数据范围：
对于100%的数据都有0<=vi<=1e5,1<=k<=n
对于40%的数据：3<=n<=100,n-1<=m<=200
对于另外40%的数据：3<=n,m<=1e4,n-1<=m<=2e4
对于剩下20%的数据：3<=n,m<=1e5,n-1<=m<=2e5
经过10时间，所有的节点都申请完了IP。报文从1号节点经过4号传递到5号，用时4，总计14。
