"With" is a preposition, so starting a sentence with it is not "natural". In your example, "with many of tourist returning from the sure due to bad weather" is a prepositional phrase that acts as an adverb modifying "decided". The "natural" place to put an adverb is next to the verb it is modifying, but "with" has developed the meaning as implying causation when it precedes the verb that it modifying, so this phrase is put in front to give that meaning. When an adverbial phrase is moved to the front like this, it should be followed by a comma. Also, "many of tourist" is not grammatical. Perhaps "many a tourist" is meant. It could also be "many of the tourists". Also, I would put "to not visit" rather than "not to visit"; the latter seems to be motivated by the idea that there's something wrong with "split infinitives". Also, "due to" is here being used as an adverb, and there is a school of thought that says that it should be used as an adjective (that is, only be used to modify nouns or be the subject complement of a copula).