Frattini subgroup of $p$-group

Question

Suppose $G$ is a finite, non-trivial $p$-group and $\Phi(G)$ is the Frattini subgroup, defined as the intersection of all maximal subgroups of $G$. Since $G$ is finite, there are finitely many maximal subgroups, $M_1, ..., M_k$.
My goal is to show that $M_1 \cap ... \cap M_{j-1} \cap M_{j+1} \cap ... \cap M_k \setminus M_j$ is non-empty for each $j = 1,..., k$. I was able to prove that any maximal subgroup of $G$ is normal and has index $p$. But, it is not clear how to proceed.
I would appreciate any hint.