Well i think if Tsunade could do it (considering her crazy gambling habits), Naruto can do it sooner or later. They first came to Jirayai too, who was by no argument the strongest nin in Konoha at the time. They came to him almost immediately saying we need a "strong leader". A powerful leader not only is able to protect the village, but gives hope to the people, leaving a sense of comfort.