INT_MAX + 1 = INT_MIN, you can imagine it as a cycle. So when your program check for the 5th edge, i.e "5 3 20", both dist[5] and dist[3] are equal to INT_MAX, so INT_MAX + edge.weight will return to negative value.

You can fix it easily. Instead of assigning every element equal to INT_MAX, you should assign them equal to a big enough number, for example 10^9 + 7 is good.