题目背景

WTX通过你的帮助找到了CodingCow的IP和电话号码，现在他准备去顺着网线爬到CodingCow家里给他一个惊喜。

题目描述

WTX目前有一个广东的光纤分布图，是一个不含负权边的图。他知道自己的位置和CodingCow的位置。请你帮他计算出他要爬多长的光纤。

题目格式

输入

第一行输入两个整数n、m和e，分别代表点数和边数，WTX在第1个点，CodingCow在第e个点。

第2到m+1行，各输入三个整数u，v，w 代表表示从u到 v 有一条权值为 w 的有向边。

输出

WTX爬光纤去CodingCow家最少需要爬多长的光纤，如果到不了，请输出2139062143

Samples

5 3 4
1 2 5
2 4 3
1 4 7

7

Limitation

$m≤2000$