Graduate Work Matters

To prove that writing graduate work is important, you decided to invent some interesting problem connected to it: You are given a weighted complete **undirected** graph on $N$ nodes. For every pair of vertices $(i, j)$ with $1 \le i \lt j \le N$ there is an edge with weight $D \cdot |i - j| + c_{ij}$ between them, with $0 \le c_{ij} \lt D$ (remember, that graph is undirected, so there will be edg