import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeSet;
import java.util.stream.Collectors;

class Ideone {
	public static void main(String[] args) {
		test1();
		test2();
	}
	public static void test1() {
		Graph graph = new Graph();
		graph.addEdge(0, 1, 4);
		graph.addEdge(0, 2, 3);
		graph.addEdge(1, 2, 1);
		graph.addEdge(1, 3, 2);
		graph.addEdge(2, 3, 4);
		graph.addEdge(3, 4, 2);
		graph.addEdge(4, 5, 6);
		graph.startAt(0);
		System.out.println(graph.getPath(5));
	}
	public static void test2() {
		Graph graph = new Graph();
		graph.addEdge(0, 1, 4);
		graph.addEdge(0, 2, 3);
		graph.addEdge(1, 3, 2);
		graph.addEdge(1, 2, 5);
		graph.addEdge(2, 3, 7);
		graph.addEdge(3, 4, 2);
		graph.addEdge(4, 0, 4);
		graph.addEdge(4, 1, 4);
		graph.addEdge(4, 5, 6);
		graph.startAt(0);
		System.out.println(graph.getPath(5));
	}
}
final class Graph {
	private static final class Node {
		final int no;
		Map<Node, Integer> edges = new HashMap<>();
		Node[] path;
		int pathWeight;
		Node(int no) {
			this.no = no;
		}
	}

	private Map<Integer, Node> nodes = new HashMap<>();

	public void addEdge(int sourceNo, int destinationNo, int weight) {
		Node source = this.nodes.computeIfAbsent(sourceNo, Node::new);
		Node dest = this.nodes.computeIfAbsent(destinationNo, Node::new);
		source.edges.put(dest, weight);
		dest.edges.put(source, weight);
	}

	public void startAt(int startNo) {
		this.nodes.values().forEach(n -> n.path = null);
		Node source = this.nodes.computeIfAbsent(startNo, Node::new);
		source.path = new Node[] { source };
		source.pathWeight = 0;
		TreeSet<Node> pending = new TreeSet<>((a, b) -> Integer.compare(a.pathWeight, b.pathWeight));
		pending.add(source);
		while ((source = pending.pollFirst()) != null) {
			for (Entry<Node, Integer> edge : source.edges.entrySet()) {
				Node dest = edge.getKey();
				int weight = source.pathWeight + edge.getValue();
				if (dest.path == null || weight < dest.pathWeight
				                      || (weight == dest.pathWeight && source.path.length + 1 < dest.path.length)) {
					if (dest.path != null)
						pending.remove(dest);
					dest.path = Arrays.copyOf(source.path, source.path.length + 1);
					dest.path[source.path.length] = dest;
					dest.pathWeight = weight;
					pending.add(dest);
				}
			}
		}
	}

	public String getPath(int endNo) {
		Node node = this.nodes.get(endNo);
		return (node == null || node.path == null ? "Unreachable" :
		        Arrays.stream(node.path).map(n -> String.valueOf(n.no)).collect(Collectors.joining(" - "))
		        + " (distance: " + node.pathWeight + ")");
	}
}