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\}$.