2832: 杀了那头牛！
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：142
解决：1
题目描述
有一头可恨的大牛牛，偷吃了好多牧草，豪豪哥想要走最少的路追到它，它想请你帮助他！
牧场是一张很大的图，图中有许多房子和道路，每个房子有一个编号 $i$，每条道路连接两个房子，但是道路很简单长度不是 1 就是 2。
牛牛藏匿在了编号为 $k$ 的房子中，豪豪哥现在站在编号为 $1$ 的房子中，请你帮助他 please！
牧场是一张很大的图，图中有许多房子和道路，每个房子有一个编号 $i$，每条道路连接两个房子，但是道路很简单长度不是 1 就是 2。
牛牛藏匿在了编号为 $k$ 的房子中，豪豪哥现在站在编号为 $1$ 的房子中，请你帮助他 please！
输入
第 1 行 3 个整数 $n$，$m$，$k$ 表示有 $n$ 个房子，$m$ 条道路。牛牛藏匿在了编号为 $k$ 的房子中
第 2 ~ $m$ + 1 行，每行 3 个整数 $i$，$j$，$w$，表示有一条长度为 $w$ 的连接 $i$ - $j$ 的道路。
第 2 ~ $m$ + 1 行，每行 3 个整数 $i$，$j$，$w$，表示有一条长度为 $w$ 的连接 $i$ - $j$ 的道路。
输出
输出最短的路径。
样例输入 复制
3 2 3
1 2 1
2 3 2
样例输出 复制
3提示
$n$ 不超过 100000，$m$ 不超过 1000000，保证每道题都有至少一条路径找到牛牛