Shape memory materials can open new design opportunities in fields as diverse as healthcare, transportation or energy generation. In this respect, shape memory polymers (SMPs) have attracted much attention due to their advantages over metals in terms of weight and reliability. However, they are still marred by slow reaction times and poor mechanical performance. In this work we show how, by integrating a graphene network in a SMP matrix, it is possible to create composites with very low carbon contents (below 1 wt%) able to change shapes in short times (10 s of seconds) in response to low electric voltages (<10 V). This is possible because the conductive network is highly interconnected at the microscopic scale, acting as a very efficient Joule heater. The composites exhibit excellent shape fixity (>0.95 ± 0.03) and shape recovery ratios (>0.98 ± 0.03). Due to the 2D nature of graphene, this network directs crack propagation during fracture resulting in materials that retain bending strengths close to 100 MPa and exhibit significant extrinsic toughening (with toughness that reach values up to 3 times the initiation value). Furthermore, changes in conductivity can be used to follow the formation and growth of damage in the material before catastrophic failure, allowing the use of this material as a damage sensor. These results provide practical guidelines for the design of reliable shape memory composites for structural and sensing applications.