Sarkari Karyalay

A country has $N$ cities connected to each other with $M$ roads, like a graph with bidirectional weighted edges such that it is always possible to travel from one of the cities to other. There are $K$ government offices all located in different cities. $i^{th}$ office is located in the city $a_i$ and has $b_i$ employees. There is a restriction that each office should have at least $1$ employee.