0216. Ptz

Input file name:	f.in
Output file name:	f.out
Time limit:	2 s
Memory limit:	64 megabytes

When scientists discovered the real rules of hyperspace physics, they were quite surprised to see that neither rules of classical Newton mechanics, nor Maxwell and Einstein laws had anything in common with what happens there: The scientists discovered that hyper-universe consists of Pure Tetra Zeons (PTZ) – particles of eternal void formerly known as hyper-space-particles. PTZs can travel through P-lanes - bidirected hyper-links connecting two T-junctions. Each P-lane has some fixed Z-value associated with it. PTZs themselves at any moment have five parameters: current T-junction PTZ is located in, current Z-value of PTZ (PTZs also have Z-value like P-lanes do), minimal Z-value acquired so far, maximal Z-value acquired so far and remaining energy. When PTZ enters P-lane with Z-value less than minimal acquired Z-value so far or greater than maximal acquired Z-value so far (meaning Z-values of PTZ it had during its life), then it loses energy amount which equals to the absolute difference between current Z-value of PTZ and newly acquired minimal or maximal Z-value. If P-lane has Z value in between min/max PTZ Z-values (inclusive), no energy is lost. If PTZ has insufficient energy to enter P-lane, it cannot enter it. PTZ also can travel with any non-negative amount of energy. After exiting any P-lane, Z-value of PTZ equals to Z-value of P-lane it had just left. When PTZ is spawned at some junction, it must immediately enter some P-lane and all 3 Z-values of PTZ (current, min and max) will be equal to Z-value of entered P-lane. No energy is lost upon this initial entry.

Well, enough theories. Scientists have managed to control the way PTZ enters one or another P-lane at each T-junction. Your task is: given initial and destination T-junctions, find the minimal energy required for PTZ to reach it or state that this is impossible. PTZ starts its journey at some P-lane originating from initial T-junction with Z-values of that P-lane and at some moment it must enter the destination T-junction.

Input file

The first line contains 2 numbers: N and M - the number of T-junctions and the number of P-lanes correspondingly. 1 ≤ N, M ≤ 128. M lines follow. Each of these lines describes a single P-lane in the form V1 V2 Z where V1 is the source T-junction, V2 is the target T-junction and Z is P-lane's Z-value. 1 ≤ V1, V2 ≤ N, |Z| ≤ 1'000'000. The final line contains IV and DV, 1 ≤ IV, DV ≤ N. IV is the initial T-junction and DV is the destination T-junction. All input values are integers.

Output file

Output a single integer - the minimal energy required for PTZ to travel from initial T-junction to the destination T-junction or line "e=m*c*c" (without quotes) if it is impossible to get from initial T-junction to destination T-junction.

Example:

f.in	f.out
5 4 1 2 1 2 3 5 3 4 3 4 5 0 1 5	7

Source: Petrozavodsk Winter 2004. Denis Koshman Contest, Saturday, January 31
Author: Denis Koshman

Discuss       Submit a solution



Printable version