[elikoga]

The $n$ in the title refers to the amount of edges.

[klyrs]

You're talking past the parent's point. If the integer weights grow faster than n*, then this algorithm will grow faster than O(n)

* integer weights measured in bit-count; log factors from multiplication time ignored