Call the original ~m~ edges ordinary edges. They all have positive weight. The extra edges between pairs of special vertices are teleport edges, each with weight ~t~.

First, compute the shortest ordinary-only path from vertex ~1~ to vertex ~n~. This path is one possible answer, and it is also useful in the cases below.

Case 1: ~t \geq 0~

In an optimal path, the teleport edges can be assumed to form one consecutive block.

To see why, suppose the path uses a teleport edge, then some ordinary edges, and later another teleport edge. The ordinary edges between those two teleport edges go from one special vertex to another special vertex. Since every pair of special vertices has a teleport edge, we can replace that whole middle part with one teleport edge. Because ordinary edges have positive weight and ~t \geq 0~, this does not make the path worse.

So the path has this form:

\[ 1 \leadsto v \quad \text{using ordinary edges, then one teleport edge, then} \quad u \leadsto n \]

where ~v~ and ~u~ are special vertices.

Run Dijkstra on the ordinary graph from vertex ~1~, and run it again from vertex ~n~. Let these distance arrays be ~d_1~ and ~d_n~.

The best path using a teleport has cost:

$$\displaystyle \min_{v \neq u,\ v,u\text{ special}} d_1[v] + t + d_n[u]. $$

This minimum can be found by keeping the best and second-best reachable special vertices from each side, or simply by trying all pairs under the given constraints.

The answer for this case is the minimum of:

• the ordinary-only shortest path from ~1~ to ~n~;
• the best path that uses one teleport edge.

If neither exists, the answer is Impossible.

Case 2: ~t < 0~

The teleport edges still form one consecutive block. Now, since every teleport edge has negative weight, if the path uses any teleport edge, it is always optimal to pass through all special vertices inside that block.

If there are ~k~ special vertices, the teleport block then uses exactly ~k-1~ teleport edges, contributing:

$$\displaystyle (k-1)t $$

to the total cost. This value is fixed, so we only need to minimize the total weight of the ordinary parts of the path.

The path has this form:

\[ 1 \leadsto v \quad \text{using ordinary edges, then all special vertices by teleports, then} \quad u \leadsto n \]

where ~v~ and ~u~ are two special vertices. The two ordinary parts must be vertex-disjoint; otherwise their union would not form a simple path.

Because the ordinary graph is undirected, this is equivalent to finding two vertex-disjoint ordinary paths:

• one path from vertex ~1~ to a special vertex;
• one path from vertex ~n~ to a different special vertex.

with minimum total cost.

This can be solved with min-cost flow.

Build a directed flow network from the ordinary graph:

1. Split every vertex ~x~ into ~x_{in}~ and ~x_{out}~, and add an edge ~x_{in} \to x_{out}~ with capacity ~1~ and cost ~0~. This enforces vertex-disjointness.
2. For every ordinary undirected edge ~(u,v)~ of weight ~w~, add the directed edge ~u_{out} \to v_{in}~ if ~u~ is not special, and add the directed edge ~v_{out} \to u_{in}~ if ~v~ is not special. Each added edge has capacity ~1~ and cost ~w~. This lets a path enter a special vertex, but once it reaches one, it stops there.
3. Add a source ~s~ with edges to ~1_{in}~ and ~n_{in}~, each with capacity ~1~ and cost ~0~.
4. Add an edge from every special vertex ~x_{out}~ to the sink ~q~, with capacity ~1~ and cost ~0~.

Now find the minimum-cost flow of value ~2~. If such a flow exists, its cost is exactly the minimum total ordinary-edge cost of the two required vertex-disjoint paths. The corresponding full path has cost:

$$\displaystyle \text{flow cost} + (k-1)t. $$

Again, compare this value with the ordinary-only shortest path.

Complexity

For ~t \geq 0~, two Dijkstra runs are enough:

$$\displaystyle O((n+m)\log n). $$

For ~t < 0~, the min-cost flow sends only ~2~ units of flow. Using shortest augmenting paths with Bellman-Ford or SPFA on the residual graph gives:

$$\displaystyle O(nm). $$

Finally, if no candidate path exists, print Impossible; otherwise print the minimum candidate value.