Robotic Path Optimization

In a robot manufacturing warehouse, a robot must travel from a designated start section to a goal section while picking up necessary parts. The warehouse is modeled as an undirected weighted graph where each node represents a section and each edge carries a travel time cost. Given (n) nodes and (m) edges, along with a starting node (s) and destination node (t), your task is to compute the minimum travel time required to get from (s) to (t). If no such path exists, output "Impossible".

The problem can be formulated mathematically as finding the shortest path in a graph. That is, if (d(u,v)) represents the minimum cost between nodes (u) and (v), you are required to compute (d(s,t)), or determine that (d(s,t)=\infty), in which case you print "Impossible".

inputFormat

Input is read from standard input (stdin) and consists of multiple datasets. Each dataset begins with a single line containing four integers (n), (m), (s), and (t), where (n) is the number of nodes, (m) is the number of edges, (s) is the starting node, and (t) is the destination node. The next (m) lines each contain three integers (u), (v), and (c), which denote an undirected edge between nodes (u) and (v) with a travel time of (c). A dataset with the line "0 0 0 0" signals the end of input.

outputFormat

For each dataset, output a single line to standard output (stdout) containing the minimum travel time from (s) to (t), or "Impossible" if no path exists.## sample

4 5 1 4
1 2 10
1 3 15
2 4 10
3 4 10
3 2 5
0 0 0 0

20