A communication device may execute an output control process for externally outputting output information obtained by using a public key, receive an authentication request in which the public key is used from a terminal device, send an authentication response to the terminal device, receive N pieces of wireless setting information from the terminal device, send, by using each of the N pieces of wireless setting information, a confirm signal to an access point corresponding to each of the N pieces of wireless setting information, receive a response signal in response to sending the confirm signal from each of M access points among N access points, select a target access point from among the M access points, and establish a wireless connection with the target access point.