时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给定一个无向图，有 \(n\) 个点和 \(m\) 条边。现在给你一个起点 \(s\)，请你求出一棵生成树，这棵树以 \(s\) 为树根，令 \(s\) 到 \(i\) 的最短路长度为 \(a\)，在生成树中 \(s\) 到 \(i\) 的简单路径长度为 \(b\)，你需要保证对于任意的 \(i\)，都有 \(a=b\)。

　　最短路径树可能不唯一，你需要在最短路径树的基础上，保证所有你选中的边的总边权和最小，输出这个边权和。

【输入格式】

　　第一行三个正整数 \(n,m,s\)，如题目描述所说。
　　接下来 \(m\) 行，每行三个正整数 \(u,v,w\)，表示 \(u\) 与 \(v\) 之间存在一条长度为 \(w\) 的无向边。

【输出格式】

　　输出一行，一个整数表示总边权和最小的最短路径树。

【输入输出样例】

　Input

3 3 1
1 2 3
2 3 1
1 3 2

　Output

3

【输入输出样例解释】

　　注意到我们可以选择边为 1−2 与 1−3 的最短路径树，此时总边权和是 3+2=5。但是如果我们选择 1−3 与 2−3 这两条边，虽然也是最短路径树，但是总边权和是 2+1=3，显然更小，所以我们选择后者。

【数据限制】

　　对于 \(100\%\) 的数据，\(n⩽2×10^5，m⩽min{2n(n−1),5×10^5}\)，我们保证这个图没有重边没有自环且连通。\(1⩽u,v,s⩽n,1⩽w⩽10^9\)。

【来源】

　　Mr.he