This is a graph theory problem that all comes down to casework. It is good practice for many contest problems where we can make life easier by pruning out all of the trivial cases first before making bigger decisions.

The network of towns and roads can be represented as a directed, weighted graph. First we will need to determine the shortest distance from each town to each of the two contest sites. Finding shortest paths is a well-known problem in computer science, and many great online tutorials can be easily found. Two algorithms for finding the pairwise distance between every node in the graph are the Floyd-Warshall algorithm and Dijkstra's algorithm. The former is very simple to code and runs in ~\mathcal O(N^3)~ time while the latter will run for ~\mathcal O(M \log N)~ per starting node, or ~\mathcal O(NM \log N)~ if we run it starting from all ~N~ nodes. However, since ~N~ is as big as ~10^5~, both of these methods will not run in time for larger cases. To obtain full marks, we can simply reverse the directions of all edges in the graph, and then run Dijkstra's algorithm backwards from the two contest sites. This will give us the distances from every node to the contest sites in merely ~\mathcal O(M \log N)~ time.

Now that we have the distances from every town to the contest sites, we can individually consider each town ~i~ with more than ~0~ competitors. Let's say for a town, the distance to the main site is ~D_1~ and the distance to the secondary site is ~D_2~. There are 4 possible cases:

• ~D_1 = D_2 = \infty~. This means we cannot reach either of the contest sites from the town we're currently examining. Immediately, we know that there is no way to distribute all the contestants.
• Only ~D_1 = \infty~. Since we cannot reach town ~1~, we know that we must send the competitors from this town to ~D_2~. This is yet another trivial case we can get out of the way.
• ~D_1 \le D_2~. Since the main site is as close or closer to the secondary site, and sending competitors has no downside, we might as well send everyone from this town to the main site.
• ~D_1 > D_2~. This is the toughest case because we have to make a decision. It requires less distance for competitors in this town to attend the secondary site, but not necessarily all of them can do it considering the limit of ~K~. We know for every competitor in this town that attends the main site over the secondary site, they will have to travel an excess distance of ~D_1-D_2~ compared to those who attend the secondary site. The solution is to sort all of the towns by decreasing value of ~D_1-D_2~ (the sacrifice to attend the main site over the secondary), and send as many competitors from the beginning of this sorted list as possible to the secondary site, until we run out of capacity there. Then we send the remainder to the primary site.