The answer is $34$.
Let $A_1, A_2, \dots, A_{35}$ be cities so that only $A_i$ and $A_{i+1}$ are connected for $i = 1, 2, \dots, 34$. The travel between $A_1$ and $A_{35}$ uses at least $34$ flights. After adding flights between $A_1$ and $A_{35}$, it is possible to travel between any pair of cities by using at most $17$ flights. Therefore, the answer is at least $34$.

Let us show that $34$ flights are sufficient. Let $\rho(X, Y)$ denote the minimal possible number of flights between the cities $X$ and $Y$. On the contrary, suppose that $\rho(A, B) > 34$ for some cities $A$ and $B$ and a path with minimal number of flights before adding a flight between the cities $T$ and $S$ is $(A = A_0, A_1, \dots, A_{17}, A_{18}, \dots, B = A_k)$. After adding the flight between $T$ and $S$, $\rho(A, A_{18}) \le 17$ and $\rho(A_{17}, B) \le 17$. By definitions, both of the paths with minimal number of flights from $A$ to $A_{18}$ and from $A_{17}$ to $B$ have to use the flight between $T$ and $S$. Without loss of generality we may assume that the path from $A$ to $A_{18}$ is $(A_0, \dots, T, S, \dots, A_{18})$. Then note that $l_1 + l_2 \le 16$ where $\rho(A, T) = l_1$, $\rho(S, A_{18}) = l_2$.

Similarly, the path from $A_{17}$ to $B$ is $(A_{17}, \dots, T, S, \dots, B)$ with $\rho(A_{17}, T) = m_1$, $\rho(S, B) = m_2$ and $m_1 + m_2 \le 16$, or the path from $A_{17}$ to $B$ is $(A_{17}, \dots, S, T, \dots, B)$ with $\rho(A_{17}, S) = k_1$, $\rho(T, B) = k_2$ and $k_1 + k_2 \le 16$. Then there exists a travel from $A$ to $B$ $(A, \dots, T, \dots, A_{18}, A_{17}, \dots, S, \dots, B)$ using at most $l_1 + m_1 + 1 + l_2 + m_2 < 34$ flights or $(A, \dots, T, \dots, B)$ using at most $l_1 + k_2 < 34$ flights. Contradiction.