Notice that because this new vertex S has no edges going into it, it's effectively invisible from the perspective of all of the original vertices in the graph G. So in particular, the shortest path distance between any pair of vertices U and V in the original graph is unchanged by this addition of the vertex S. Similarly, whether or not G has a negative cycle, it's unaffected by the addition of the vertex S. The next step of Johnson's 