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