D - Round-Trip Delivery Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は配送会社でアルバイトをしています。この地域には N 個の配送拠点があり、拠点には 1 から N までの番号が付けられています。

この地域には M 本の道路があり、i 番目の道路は拠点 A_i と拠点 B_i を双方向に結んでいます。この道路を通ると、どちらの方向に進んでも C_i 分の時間がかかります。

高橋君は今日、本社のある拠点 1 を出発し、拠点 T にいる顧客のもとへ荷物を届けてから、拠点 1 に戻らなければなりません。

具体的には、高橋君は拠点 1 から出発して道路を順にたどって移動し、移動中に拠点 T を少なくとも 1 回訪れたうえで、最終的に拠点 1 に戻ります。途中で他の拠点を経由しても構いませんし、同じ道路や同じ拠点を複数回通ることも許されます。同じ道路を複数回通った場合、通るたびにその道路の所要時間が加算されます。

このとき、拠点 1 を出発してから拠点 1 に戻るまでに通った道路の所要時間の合計として考えられる最小値を求めてください。

ただし、条件を満たす経路（拠点 1 を出発し、拠点 T を少なくとも 1 回訪れて拠点 1 に戻る経路）が存在しない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 2 \leq T \leq N
  • 1 \leq A_i < B_i \leq N（特に自己ループは存在しない）
  • 1 \leq C_i \leq 10^9
  • 同じ拠点の組を結ぶ道路は高々 1 本である
  • 入力は全て整数である

入力

N M T
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M
  • 1 行目には、拠点の数 N 、道路の数 M 、必ず訪れるべき拠点の番号 T が、スペース区切りで与えられる。
  • 続く M 行のうち i 行目には、i 番目の道路が結ぶ 2 つの拠点の番号 A_i , B_i と、その道路を通るのにかかる時間 C_i が、スペース区切りで与えられる。

出力

高橋君が拠点 1 を出発し、拠点 T を少なくとも 1 回訪れてから拠点 1 に戻るまでにかかる最小の合計時間を 1 行で出力せよ。条件を満たす経路が存在しない場合は -1 を出力せよ。

入力例 1

4 4 3
1 2 5
2 3 3
3 4 2
1 4 10

出力例 1

16

入力例 2

5 3 5
1 2 100
3 4 50
4 5 30

出力例 2

-1

入力例 3

6 8 4
1 2 10
1 3 15
2 3 5
2 4 20
3 4 8
3 5 12
4 6 6
5 6 3

出力例 3

46

Score : 400 pts

Problem Statement

Takahashi works part-time at a delivery company. There are N delivery hubs in this area, numbered from 1 to N.

There are M roads in this area, and the i-th road connects hub A_i and hub B_i bidirectionally. Traveling along this road takes C_i minutes in either direction.

Today, Takahashi must depart from hub 1, where the headquarters is located, deliver a package to a customer at hub T, and then return to hub 1.

Specifically, Takahashi starts at hub 1, travels along roads in sequence, visits hub T at least once during the journey, and ultimately returns to hub 1. He may pass through other hubs along the way, and he is allowed to traverse the same road or visit the same hub multiple times. If the same road is traversed multiple times, the travel time for that road is added each time it is traversed.

Find the minimum possible total travel time of the roads traversed from the time Takahashi departs hub 1 until he returns to hub 1.

If no valid route exists (a route that departs from hub 1, visits hub T at least once, and returns to hub 1), output -1.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 2 \leq T \leq N
  • 1 \leq A_i < B_i \leq N (in particular, there are no self-loops)
  • 1 \leq C_i \leq 10^9
  • There is at most one road connecting any pair of hubs
  • All input values are integers

Input

N M T
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M
  • The first line contains the number of hubs N, the number of roads M, and the hub number T that must be visited, separated by spaces.
  • The i-th of the following M lines contains the numbers of the two hubs A_i, B_i connected by the i-th road, and the time C_i required to travel along that road, separated by spaces.

Output

Output in one line the minimum total time for Takahashi to depart from hub 1, visit hub T at least once, and return to hub 1. If no valid route exists, output -1.

Sample Input 1

4 4 3
1 2 5
2 3 3
3 4 2
1 4 10

Sample Output 1

16

Sample Input 2

5 3 5
1 2 100
3 4 50
4 5 30

Sample Output 2

-1

Sample Input 3

6 8 4
1 2 10
1 3 15
2 3 5
2 4 20
3 4 8
3 5 12
4 6 6
5 6 3

Sample Output 3

46