[godwine]

4-5 weeks is a very long time to travel Japan, so you should be able to cover a lot of grounds.

I usually start from south, so if I have 5 weeks and enough money, i will start with Kyushu, try the yatai along naka river for some good street food. Kagoshima is also a nice place. You probably will need 3 days if you want to stay both in hakata and kagoshima.

Then, the next i will consider is probably to start with honshu, you could travel to shikoku from kyushu directly, but i don'tknow enough about shikoku to suggest things to see.

Miyajima and Hiroshima are also good destination

Maybe make a stop at himeji as well?

Stop by Kobe if you have time, nothing much to see, probably only need one or 2 days max to see it. Osaka ou have a lots of good food and some cool night life, but aside from the food, it really doesn't offer anything that Tokyo doesn't have, just different scenes, i usually spend 3-4 days in Osaka

Kyoto is where most of the culture, history and such will be located, tones of temples and shrines, make sure you stop by nara as well. I recommend 5 days for nara and kyoto for a nice and non rush trip

I myself usually will drop by hakone, and I love yokohama. Then it will be north to takayama, and finally tokyo......

with 5 weeks, you may also want to go to nikko, may be make your lodging arrangement in Kinugawa, i personally suggest reserving a nice japanese style room with dinner plan at Yume no Toki....

Maybe you can take a night train with sleeping coach to Sapporo and Furano as well....