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

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