I have a graph which is a sequence of edges with associated distance (travel time), as well as a start and destination node with an associated maximum allowed travel time. All edges can be traveled both ways.

I want to determine the single shortest path between the start and destination, and print the route if the distance of the path is equal or less than the maximum allowed travel time.

Input

Input is read from standard input and has the following characteristics:

• It is two lines; the first line describes the edges of the graph: Each edge is formatted as an opening bracket '[', the first node of the pair, a comma, the second node of the pair, another comma, the distance between the nodes, followed by a closing bracket ']'. Example: '[A,B,5]'
  Representation
• The second line describes the start and destination node, as well as the maximum allowed travel time. The starting node, followed by an ASCII arrow '->' (two characters), the destination node, a comma, and the maximum allowed travel time. Example 'A->D,5'
  Representation
• Leading or trailing whitespace is not allowed.
• All nodes are single, uppercase letters.
• Edges are separated by a single space.
• Distances are specified as unsigned integers.
• The sequence of edges is not ordered in any specific way.

Output

Output is written to standard output and must have the following characteristics:

• It is one line.
• It contains no whitespace.
• If errors are present, print the first of the below listed errors (e.g. if bot E2 and E3 are present, print "E2").
• If no errors are present, print the route using the representation as described below.

Errors

You should detect the following errors:

Code - Type

E1 - Input syntax error

E2 - Logical input error

E3 - Failed to find a suitable route

Logical input errors are: duplicate definitions of edges, specifying either a start or destination node (second line) that is not actually defined in the graph (first line), disconnected graphs, or more than one shortest path found.

Output Representation

If there were no errors and the shortest route is found, the nodes should be printed in traveling order, including the start and destination, separated by ASCII arrow '->' (two characters).

Sample Input #00

[A,B,3] [B,C,5] [C,D,2]
A->D,10

Sample Output #00

A->B->C->D

Sample Input #01

[A,B,3] [A,C,7] [C,D,2] [B,C,5]
A->D,10

Sample Output #01

A->C->D

Sample Input #02

[A,B,5] [A,C,2] [B,C,4] [B,D,6] [C,B, 7]
A->C,10

Sample Output #02

E2

Output #2 Explanation

The last edge [C,B,7] on the line is a re-definition (duplication) of a previously defined edge [B,C,4]. Such duplication should result in a logical input error.

I can choose between C++ and Java. This is the default input for Java:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static void main(String args[] ) throws Exception {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */
        
    }
}