How is Johnson's shortest path weighting function $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$ proven by the triangular inequility? Recap to the Johnson's shortest path algorithm:

By the procedure extending the original graph $G^\prime = (V^\prime, E^\prime), V^\prime = V\ \cup \{s\}, E^\prime = E\ \cup \{(s, v)\ |\ \forall v \in V\}$, and then extend the original weighting function $\forall x \in V,\ w(s, x) = 0.$

Finally define the reweighted function $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$ where $\forall x \in V,\ h(x) = d(s, x)$ , where $d(s, x)$ is the shortest path from $s$ to $x$.

Problem: 

Assume that there is no negative cycle in the graph. The textbook Introduction to Algorithms says that
$w(u, v) + h(u) - h(v)$ is always nonnegative proven by using the triangular inequality theorem to get $w(u, v) + h(u) \ge h(v)$.

This makes me so confused, because I think that there could exist negative weights in the graph and hence triangular inequality can't be applied. (Am I misunderstanding triangular inequality? Or something are skipped I cannot tell?).

Where did I misunderstand about this algorithm? Thanks!
You're right that you can't (necessarily) apply the triangle inequality to the edges of the original graph, but that's not what's being discussed here.

We know $h(u)$ is, by definition, the shortest path to $u$.  Thus we immediately know that $w(u,v) + h(u) \geq h(v)$ because, if it wasn't true, $h(v)$ would not be the shortest path to $v$.  The author is calling this the "triangle inequality" of the reweighted graph.