Farthest Room Problem

You are given a graph representing a series of rooms connected by weighted bidirectional pathways. The goal is to find the room that is the farthest from a given starting room when considering the shortest paths. In the event of a tie (multiple rooms at the same maximum distance), choose the room with the smallest index.

Recall that the shortest path distance is defined as: $$d(v)=\min_{(u,v)\in E}(d(u)+w(u,v))$$ where \(w(u,v)\) is the weight of the edge connecting room \(u\) and room \(v\). This problem can be efficiently solved using Dijkstra's algorithm.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers \(n\) and \(m\), representing the number of rooms and the number of pathways respectively.
• The next \(m\) lines each contain three integers \(u\), \(v\), and \(w\), indicating a bidirectional pathway between room \(u\) and room \(v\) with weight \(w\).
• The last line contains an integer \(s\) which denotes the starting room.

outputFormat

The output should be written to standard output (stdout) as two integers separated by a space:

• The first integer is the room number that has the maximum shortest path distance from the starting room.
• The second integer is the corresponding shortest path distance.

4 3
0 1 1
1 2 2
1 3 2
0

2 3