a. u- u 1. Use the algs4.5tclln class for input and the algs4.Sthut class for output. Best distances program In this assignment, you are given three data files: acities.txt: List of Midwestern cities amajorcities.txt: List ofthose cities that are major hubs aconnectionsbtt: List of direct connections between those cities Download and place these les into the Eclipse data directory. 1Write a program called BestDistances.java that: Reads the list of cities into a string array using 5td|n.readAll5'lringsjj and then builds a symbol table where the key is the name oFa city and the value is an integer from U to the number of cities minus one. The rst city has value i], the second has value Land so Forth. Reads the list of major cities into a string array using Stdln.readAllStringsjj. Creates an empty undirected graph using the class algs4.Graph. In this graph, each vertex represents a city. As we discussed, the vertices of an undirected graph are labelled with nonnegative integers. When the vertices represent real world objects, this makes it difficult to connect a vertex's integer label with its real world label. You will use the symbol table just constructed to make this connection. - Reads in each connection from the connections data le, one line at a time, where each line contains the names of two cities. As it reads in each line, it adds an edge to the graph. To do this, it will have to translate From the cities given on each connection line to their corresponding vertex numbers. Prints a header line for the table to follow (see code below for printing this header). Then, iterating over the list of cities, the program Creates a BreadthFirstPaths object with that city as the starting vertex. For each major city, prints the shortest distance from the major city to the city in the outer loop Here is an example of the first few lines of expected output: Chicago KansasCity Milwaukee Minneapolis SaintLouis Alton 00 W Appleton UIGNO Carbondale 10 11 Carlinville To print the header line, use code something like this: StdOut.printf("%205", ""); for (String majorCity: majorCities) { StdOut.printf("%-12s", majorCity); } StdOut.printIn(); Print each numeric entry in the table formatted using the format string %3d ". That's four spaces before the specifier and five after