Figure 1: The weighted directed graph G. 1