Learn Arabic (Modern Standard): بدوا متعبين بعد الرحلة.

You are thinking of the verb for started, which is بدأوا and is spelled with a hamza. The verb here is بدوا without a hamza, which comes from the verb بدا meaning to seem or to appear.

Why is there an alif at the very end of بدوا?

That silent alif is written after the plural letter و suffix on verbs. It serves as a visual marker to show that the و means a plural they did it, rather than just being a normal letter at the end of a root word.

Why is the word for tired written as متعبين instead of متعبون?

Because it describes the state or condition the people were in when the action happened. In Arabic, a word that describes how someone is during an action takes the accusative case. For regular masculine plurals, this means using the ين ending instead of ون.

How does the word بعد affect the noun that follows it?

Words for time or place like بعد act like the first part of a possession phrase, known as an idafa. This forces the noun following it, الرحلة, to take the genitive case, meaning it would end with a kasra or short i sound if you pronounced the formal vowel ending.