Sensitivity-based distributed programming (SBDP) is an algorithm for solving large-scale, nonlinear programs over graph-structured networks. However, its convergence depends on the coupling strength and structure between subsystems. To address this limitation, we develop an algorithmic variant: SBDP+. The proposed method utilizes first-order sensitivities and primal decomposition to formulate low-dimensional, decoupled subproblems, which are solved in parallel with neighbor-to-neighbor communication. SBDP+ differs from SBDP by enforcing convergence for all coupling structures through a carefully designed primal-dual update. It retains a low communication effort and handles couplings in the objective and constraints. We establish sufficient conditions for local convergence in the non-convex case. The effectiveness of the method is shown by solving various distributed optimization problems, including statistical learning, with a comparison to state-of-the-art algorithms.