We show that viscoelastic plane Poiseuille flow becomes linearly unstable in the absence of inertia, in the limit of high elasticities, for ultra-dilute polymer solutions. While inertialess elastic instabilities have been predicted for curvilinear shear flows, this is the first ever report of a purely elastic linear instability in a rectilinear shear flow. The novel instability continues upto a Reynolds number ($Re$) of $O(1000)$, corresponding to the recently identified elasto-inertial turbulent state believed to underlie the maximum-drag-reduced regime. Thus, for highly elastic ultra-dilute polymer solutions, a single linearly unstable modal branch may underlie transition to elastic turbulence at zero $Re$, and to elasto-inertial turbulence at moderate $Re$, implying the existence of continuous pathways connecting the turbulent states to each other, and to the laminar base state.