Run like mad, but eat nothing, and get no stronger.
Eat good foods, run like mad, and get endurance and/or strength. No payment to a trainer needed, though you will have to purchase quality foods from NPCs or fellow players (AKA cooks).
That is how I would go about things. Paying a trainer would help you 'level' up faster, but the base of body development should always be food.