We propose a definition for prime congruences which allows us to define Krull dimension of a semiring as the length of the longest chain of prime congruences. We give a complete description of prime congruences in the polynomial and Laurent polynomial semirings over the tropical semifield R_max, the semifield Z_max, and the Boolean semifield B. We show that the dimension of the polynomial and Laurent polynomial semiring over these idempotent semifields is equal to the number of variables plus the dimension of the ground semifield. We extend this result to all additively idempotent semirings. We briefly discuss an application of the construction of primes - the Nullstellensatz for tropical polynomials from our previous work.