The Colossus would be put into the graveyard because it doesn't have its "shuffle into its owner's library" ability when replacement effects would be checked.
At the moment that your Lignified Colossus dies, it's still a 0/4 with no abilities.
From the comp rules for replacement effects:
614.4. Replacement effects must exist before the appropriate event occurs—they can’t “go back in time” and change something that’s
already happened. Spells or abilities that generate these effects
are often cast or activated in response to whatever would produce the
event and thus resolve before that event would occur.
Example: A player can activate an ability to regenerate a creature in response to a spell
that would destroy it. Once the spell resolves, though, it’s too late to regenerate the
It regains its shuffle ability once it hits your graveyard (since Lignify is gone). But the time for checking replacement effects has already passed. It stays in your graveyard.