It means "just finished praying", actually written 'baru solat', but the 't' is a stop, not a completed consonant, so we "bules" don't hear it properly. ;)
It's pretty rare to write "sh" in Indonesian, it's usually written "si" or "sy", eg 'syampu' (shampoo). But in speech the 's' might sound like 'sh' sometimes. Indonesian dialects can be pretty heavy, so relying on the spelling of "schoolbook Indo" is not the best idea. Keep your hearing flexible.
'Baru' literally means 'new', but adjectives are placed after the noun. When 'baru' is placed before a verb it means the verb has just been done (=new). Eg. "I arrive... I just arrived now" = "Saya datang... saya baru datang"
'Solat' is a prayer, or also 'to pray'. So "(saya) baru solat" = "(I) just finished praying".
In comparison, a 'new prayer' is a 'solat baru'. :) I suspect it's the exact same spelling in Malaysian.