As cancer is the second leading cause of death in the United States, it is crucial to understand how tumors interact with, and remodel, the local extracellular matrix (ECM) to promote metastasis. As tumors progress, there is an increase in both the local tissue density and stiffness, remodeling the ECM. Importantly, as individual leader cells invade into the surrounding ECM, cells are constantly sensing their local surroundings and manipulating their cell shape to navigate the ECM more efficiently. While the mechanics, in particular the bulk rheology of the ECM surrounding tumors have been well studied for their physiological impacts, the micromechanical remodeling of the ECM on the individual cell level remains poorly understood. Furthermore, 3D migration of breast cancer cells in tissue scaffold is far more complicated than the canonical model of cell migration on flat (2D) surfaces. A complexity is the existence of multiple migration modes that can be activated both internally, through mechanotransduction, and externally, through physical cues from the ECM. This migration phenotype plasticity in cancer cells based on sensing their local environment, specifically the individual cell morphodynamics as cells invade into the ECM, also remains poorly understood. In this work we study 3D tumors comprised of MDA-MB-231 triple negative breast cancer cells in type 1 collagen ECM. First, by combining holographic optical tweezers and confocal microscopy on \textit{in vitro} tumor models, we show that the micromechanics of collagen ECM surrounding an invading tumor demonstrate directional anisotropy, spatial heterogeneity, and significant variations in time as tumors invade. We find that collective force generation of a tumor stiffens the ECM and leads to anisotropic local mechanics such that the extension direction is more rigid than the compression direction. Then, we examine the morphodynamics of individual cells as they invade into the surrounding ECM. We use deep-learning algorithms to automatically segment all the disseminated cells from confocal imaging stacks, and apply previously trained machine learning models to classify the cell migration phenotype based on their morphology. Combining quantitative experiments and theoretical modeling, we demonstrate the mesoscale dynamics -- closely coupled migration and phenotype dynamics of invading cancer cells, play key roles in determining the invasive potential. By systematically varying the mechanical properties of the ECM, we show consistent mesoscale dynamics in broad conditions. Overall, our results highlight the plasticity of cancer cell migration programs and underscore the effect of ECM remodeling in reciprocally regulating cancer invasion.