If $1 ≤ t ≤ c_1 b^{L_1}$ for some positive, absolute, and effectively computable constants $c_1,L$, then the least Linnik's theorem implies that the least prime in $M_t$ is less than $c_2 b^{L_2}$ for some constants $c_2,L_2$.

If $t$ is larger than a polynomial in $b$, then we use a stronger quantitative form of Linnik's theorem:  There exist positive constants $c_2,c_3,L_2$ (each absolute and effectively computable) such that if $t>c_2 b^{L_2}$, then

$\displaystyle\#\{t<p≤ 2t\colon p\equiv a\pmod{b}\}\geq c_3 \frac{t}{\sqrt{b}~\varphi(b)\log t}$,

where $\varphi(b)$ is Euler's totient function.  (This is proved in Chapter 18 of Iwaniec and Kowalski, for instance.)  Thus there would exist a prime in between $t$ and $2t$.  We can combine both cases and state that the least prime in $M_t$ is bounded by $\max\{c_2 b^{L_2},2t\}$.