A communication device may search via a first wireless interface so as to specify one or more candidate access points and send, to a terminal device, an information request for requesting the terminal device to send information for establishing a wireless connection with an experienced access point. The experienced access point is an access point having an experience of establishing a wireless connection with the terminal device. The terminal device stores use information which has been used by the terminal device for establishing the wireless connection with the experienced access point. The communication device may receive a response including a target password included in the use information from the terminal device in response to sending the information request and establish a wireless connection with a target access point among the one or more candidate access points via the first wireless interface by using the target password included in the response.