The Scenario

You are given an undirected, weighted graph. You are guaranteed that the graph is connected. You are also guaranteed that the edge weights are all positive integers.

The challenge is as follows: for each vertex in this graph, find the distance to another vertex that is furthest away from it. Note that this doesnt mean you should pick the worst possible path between those two vertices on the contrary, the path should be the shortest one between them.

In other words for every source vertex v, find the longest one of the shortest distances from v to all other vertices (see example below if this still confuses you).

The Rules

It is up to you which data structures and algorithms you employ to find these distances, but you must write all of them on your own (i.e. you cannot use Java's Standard Library -- not even a sorting algorithm).

The more elegant and efficient your implementation is, the more credit you will receive.

Specifications

Main Application

Your application should be launchable from command-line using the following syntax (once it is compiled, of course):

> java

For example, if your main method is in the class called FindWorstDistances, the name of the input file is inputFile.txt, and the name of the output file to be created is distances.txt, then running the application should work with the following command:

> java FindWorstDistances inputFile.txt distances.txt

Input File

The input file contains a representation of the graph G. It is formatted as follows:

First line contains a single integer V, which represents the number of vertices in G.

Second line contains a single integer E, which represents the number of edges in G.

The following E lines represent edges. Each one of them contains three space-separated integers. The first two integers represent the IDs of adjacent vertices, and the third integer represents the distance between them (the weight of that edge).

Example input file

Lets call this file myGraph.txt:

8

12

0 2 16

2 6 16

6 4 76

4 7 29

7 6 75

7 5 33

7 3 94

3 5 48

3 2 33

3 0 79

0 1 15

1 5 67

myGraph.txt represents a graph that looks like this:

Output File

Your output file should have exactly V lines in it (one for each source vertex). Each one of those lines should have two numbers in it:

The ID of the source vertex

The distance to the furthest vertex from it.

Example output file

Using the graph in myGraph.txt, lets suppose we run the following in the command-line:

> java FindWorstDistances myGraph.txt worstDistances.txt

The program should generate a file called worstDistances.txt:

0 108

1 123

2 92

3 110

4 123

5 97

6 97

7 107

This file can be interpreted as follows:

The vertex furthest away from vertex 0 is at a distance 108 (thats vertex 4)

The vertex furthest away from vertex 1 is at a distance 123 (yet again, vertex 4)

etc etc

The vertex furthest away from vertex 7 is at a distance 107 (vertex 0)

6 1 4 7 5 2 7 6 3 ? 1