Handling Large Weights

In some problems, edge weights are up to $10^6$ and paths can have $10^5$ edges. Maximum distance = $10^5 \times 10^6 = 10^{11}$. This exceeds $32$-bit integer range ($\approx 2 \times 10^9$). Use long long in C++ or $64$-bit integers in other languages.

Also set $dist$ initially to a value larger than any possible path, like $10^{18}$. Using $10^9$ as "infinity" might not be enough. If you add two distances during relaxation, overflow can silently produce wrong answers.