B"Ela needs to send a large package from machine 1 to machine n through a network of machines. Currently, with the network condition, she complains that the network is too slow and the package can't arrive in time. Luckily, a Wiring Wizard offered her a helping hand. The network can be represented as an undirected connected graph with n nodes, each node representing a machine. m wires are used to connect them. Wire i is used to connect machines u_i and v_i , and has a weight w_i . The aforementioned large package, if going through wire i , will move from machine u_i to machine v_i (or vice versa) in exactly w_i microseconds. The Wiring Wizard can use his spell an arbitrary number of times. For each spell, he will choose the wire of index i , connecting machine u_i and v_i , and rewire it following these steps: The rewiring of wire i will takes w_i microseconds, and the weight of the wire will not change after this operation. After a rewiring, a machine might have some wire connect it with itself. Also, the Wiring Wizard has warned Ela that rewiring might cause temporary disconnections between some machines, but Ela just ignores it anyway. Her mission is to send the large package from machine 1 to machine n as fast as possible. Note that the Wizard can use his spell on a wire zero, one, or many times. To make sure the network works seamlessly while transferring the large package, once the package starts transferring from machine 1 , the Wiring Wizard cannot use his spell to move wires around anymore. Ela wonders, with the help of the Wiring Wizard, what is the least amount of time needed to transfer the large package from machine 1 to n . Each test contains multiple test cases. The first line contains the number of test cases t ( 1 <= t <= 100 ). The description of the test cases follows. The first line contains n and "...