Next up in the OJFTMHYLW  list is seaweed. But..why not call it sea vegetables? Weed sounds so unappetizing, so unwanted. Yet, seaweed is a terrific food.
There are many kinds of seaweed commonly consumed in Japan, and all are quite low in calories, contain many minerals, and are high in fiber. The only problem for a lot of people is that seaweed has a distinctive texture and flavor.
Wakame, which often appears in salads, as garnish for sashimi, and in miso soup , has a rather slimy texture which just gets more slimy the longer it's soaked. If you can get used to this all the better of course. But if not, there are ways to get around this. First, try chopping it up very finely and sneaking it into food. Second, if you put it into soup (like for miso soup) the sliminess, which is actually a form of fiber, will melt into the liquid and be less noticeable. Also, sautéing in oil, or mixing with an acid like vinegar, counteracts the sliminess.
Kombu seaweed is most commonly used to make dashi stock , but it can also be eaten. The best way to eat kombu is to chop it up very finely unless you develop a liking for the leathery texture. You can also find kombu-cha, kombu tea, which is dried, salted and flavored pieces of kombu steeped in water.
Nori may be the most familiar seaweed since it's used as a wrapper for sushi. It's usually not cooked, though there are traditional recipes calling for softened nori. (Some people like a sort of soft nori paste to eat with rice...it is sort of like a Japanese version of Marmite.)
Kanten, or agar-agar, is a coagulant extracted from a seaweed called amakusa. It's used like gelatin, but it has slightly different coagulation properties, and is all-vegetable of course.
Then there is hijiki, which may be the most versatile seaweed of all. It's also extremely high in fiber - about 40% of it in dried form is fiber. Hijiki is not commonly seen on the menus of Japanese restaurants since it's used mostly for homely home cooking. It comes in dried form, as do most other seaweeds (except for salted 'fresh' wakame). It's usually soaked for about an hour beforehand, then rinsed, before use, If you're in a hurry though you can blanch it for a couple of minutes in boiling water, which hydrates it quite fast. Hijiki when reconstituted swells to about 5 times its original weight, so don't use too much! A serving is usually 1 or two tablespoons worth at most.
Hijiki comes in two forms mostly: regular hijiki, which is rather twig-like in dried form, and me hijiki, small buds of hijiki that looks like black tea in dried form. Once regular hijiki is reconstituted, it looks like long black noodles. Star Trek fans may see a remarkable similarity to gagh . However hijiki does not move on your plate or have feet.
The traditional way to cook hijiki is to stew it in dashi stock flavored with soy sauce and often sugar, together with vegetables like carrot or lotus root, or fried tofu (aburaage). Since it's fairly neutral in flavor, it can be used in salads, or stir fries and such.
There is just one caveat about hijiki. Four countries have issued warnings, but no outright bans, for hijiki, citing its more than accepted levels of inorganic arsenic. It should be noted that the initial tests on hijiki which lead to those warnings in the UK among other places was based on testing the dried, un-soaked hijiki - and you never eat hijiki that way. Soaking reduces the amount of trace arsenic by 1/7th; rinsing and cooking it in liquid further reduces it. The report here (Japanese) by the Tokyo Health and Welfare Department  states that as long as a person weighing 50kg (about 110lb) does not eat more than 5 servings of hijiki of 5g dry weight per serving (which swells up to a lot more than that when soaked) that it is perfectly safe, even for pregnant women.
In a nutshell, when it's prepared properly (soaked, rinsed then stewed, and eaten with vegetables) I don't believe there is much to worry about. To me the many benefits of hijiki and other seaweed far outweigh the drawbacks. If I were the UK government, I'd be issuing dire health warning about things like blood pudding, but that wouldn't be politically popular! Some weird foreign seaweed is a much easier target. (And I do like blood pudding, once in a great while.)
In any case you should not consume large quantities of this or any other food (it's actually very hard, if not impossible, to eat a huge amount of hijiki) and it's often recommended to eat it with vegetables which may help to eliminate the inorganic arsenic from the body efficiently. Pre-soaking it and rinsing it before eating, which is the traditional way to prepare it, eliminates much of the arsenic content also.
This is a non-traditional way of cooking hijiki, though note that the hijiki is still soaked, rinsed and stewed and eaten with vegetables. It adds fiber, flavor and interesting color to a pasta dish that's inspired by "Spaghetti Napolitan", a common item served in Japanese family-style restaurants and such, that has nothing at all as far as I can tell with Naples. It has tons of vegetables and a little bit of ham, which can be left out to make this a vegetarian/vegan dish.
This yields 4 generous and very filling servings.
Soak the hijiki, drain and rinse following the directions above.
Heat up a pot of water to boil the pasta.
Slice the vegetables thinly. Chop the garlic finely. Cut the ham into strips.
While you boil the pasta, heat up a sauté pan or wok. Put in the can of tomatoes and the vegetables. Simmer until the vegetables are soft and the moisture is almost gone. Add the oil and ham and hijiki and sauté briefly. Add the tomato paste and Worcestershire sauce. Season if needed with salt and pepper.
Drain the pasta and add to the pan, stir around to coat the strands well. Serve immediately, optionally topped with some freshly grated Parmesan cheese.
Don't just settle for commercial furikake  that's often loaded with MSG and other dubious ingredients. Furikake is quite easy to make at home, with only the things you want in it.
This furikake, which is just bursting with umami, can be made with any seaweed you like, or a mixture. Be sure to chop up the seaweed finely. This is most easily accomplished in a food processor, but you can chop by hand too. This one has a mixture of me-hikiji and nori. Chirimenjako is small, salted whole fish - you can find this or something similar in most Japanese, Korean or Chinese groceries. You can leave it out if tiny whole fish bother you.
Chop the seaweed up finely. (If using me-hijiki you don't need to do much chopping.)
Put the moist seaweed and the chirimenjako in a non-stick frying pan over medium heat. Stir around until it's dried out quite a bit and is getting a bit crispy but not burnt. Add the soy sauce, the bonito flakes, and the shredded nori, and continue stirring until it's almost dry. Add the sesame seeds, citrus rind and red pepper, and stir until the sesame seeds are popping. Take off the heat. Store in an airtight container in the refrigerator, and try to use it up within a week.
I find the information about seaweed in English to be rather spotty, so I've drawn most of my information from Japanese sites.