## Editorial for SAC '22 Code Challenge 4 Junior P5 - Obligatory Output Only Problem

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

There are many solutions to this problem.

The main prerequisite to solving this problem is knowing how Dijkstra's algorithm runs.

Below is an outline of a solution:

Connect to with a weight of .

Connect to with a weight of .

Finally, output , , and the edges on separate lines.

**Time Complexity:**

This graph will push into the queue many times since Dijkstra's algorithm will traverse first and then discover to is better, but then to is better, and so forth.

will check each of its adjacent edges , causing the `counter`

variable to exceed .

## Comments