Rescue Pikachu

A cunning plan by Team Rocket has kidnapped Pikachu and left a taunting message for Ash! Determined to rescue Pikachu and uphold justice, Ash and his friends set out on a daring mission. There are a total of N enemy bases (numbered 1 through N) connected by M bidirectional roads. Ash’s team of K people all start from their hometown, which is designated as vertex 0, while Pikachu is held captive at base N.

However, due to heavy enemy defenses, there is one special base – base K. In order to "destroy" (i.e. neutralize) base K, the team must first destroy bases 1, 2, …, K-1 in sequence. In particular, before base K-1 is destroyed, no one is allowed to pass through (or enter) base K (since doing so will trigger alarm and disastrous consequences). To simplify the problem, we assume that any person who passes through base K immediately destroys it. Note that once a base is destroyed it may be passed through freely.

The team is allowed to split – different members can take separate routes. In summary, the rescue plan must satisfy the following:

1. If K = 1, no ordered destructions are required. Otherwise, one or more team members must travel from vertex 0 and collectively visit bases 1, 2, …, K-1 in that exact order. When traveling to destroy these bases, base K must be avoided (i.e. it is removed from consideration).
2. After base K-1 is destroyed, another team member (who may have been waiting at vertex 0) is allowed to travel and pass through base K — thereby destroying it.
3. Finally, once base N is destroyed (by anyone entering it), Pikachu is rescued.

The goal is to minimize the total sum of road lengths traveled by the team (the members who do not move contribute 0 distance) while ensuring that the above conditions are met.

More formally, let d_F(u,v) be the shortest distance between vertices u and v in the full graph, and let d_R(u,v) be the shortest distance computed on a restricted graph where vertex K is removed. Then:

• If K = 1: The total minimum distance is d_F(0,1) + d_F(1,N) (note that base 1 is the same as base K in this case).
• If K > 1:

  Define the chain cost for bases 1 through K-1 as \[ \text{chain} = d_R(0,1) + d_R(1,2) + \cdots + d_R(K-2, K-1). \] Then, let the rescue cost be \[ \text{rescue} = d_F(0, K) + d_F(K, N). \] The answer is the sum of these two costs.

You can assume that a valid route exists for each required segment. Compute and output the minimum possible total distance.

inputFormat

The first line contains three integers N, M, and K: the number of enemy bases, the number of bidirectional roads, and the number of team members (K also plays a role in the ordered destruction constraint). The bases are numbered from 1 to N, and the starting town is vertex 0.

Then M lines follow, each containing three integers u, v, and w, representing a bidirectional road connecting vertices u and v with length w.

Note: When computing the paths for destroying bases 1 to K-1 in order, the graph is considered with vertex K removed (i.e. any road incident to vertex K is not available).

outputFormat

Output a single integer representing the minimum total distance traveled by the team to destroy the necessary bases and rescue Pikachu.

sample

5 6 3
0 1 2
1 2 3
2 3 4
0 3 10
0 2 6
3 5 1

15