题目描述

Peer Brelstet 又开始偷画了，但这个别墅呈一颗树状分布。每个别墅里的房间由若干跳过道通向其他房间。他想尽快找到画：

1. 他会从房间 \(0\) 开始找;
2. 他总是会选择离自己最近的房间找;
3. 如果没找到，则继续选最近的房间深入;
4. 如果已没有房间可走，则返回到上一个房间，继续选择（往回走也算时间）;
5. 当然，除了往回走,他是不会去一个房间两次的。

格式

输入格式

第 \(1\) 行，\(n\) 是房间个数，\(p\) 是名画所在的房间。\((p<=n<100)\)
第 \(2 \sim n\) 行，每行 \(3\) 个整数 \(s,t,l\)。从房间 \(s\) 到房间 \(t\) 的时间 \(l\)。\((s≠t, 0<=s<t< n, 0 <l<=10000)\)

输出格式

输出找到名画的时间(开始时间为 \(0\))。

样例1

样例输入1

5 2
0 1 1
0 2 2
1 3 3
1 4 4

样例输出1

18