[Solution] Ela and the Wiring Wizard Codeforces Solution

D. Ela and the Wiring Wizard

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Ela needs to send a large package from machine 1$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:

• Choose one machine that is connected by this wire. Without loss of generality, let's choose 𝑣𝑖$v_i$.
• Choose a machine that is currently connecting to 𝑣𝑖$v_i$ (including 𝑢𝑖$u_i$), call it 𝑡𝑖$t_i$. Disconnect the wire indexed 𝑖$i$ from 𝑣𝑖$v_i$, then using it to connect 𝑢𝑖$u_i$ and 𝑡𝑖$t_i$.

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$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$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$1$ to 𝑛$n$.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡$t$ (1≤𝑡≤100$1\le t\le 100$). The description of the test cases follows.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The first line contains 𝑛$n$ and 𝑚$m$ (2≤𝑛≤500$2\le n\le 500$, 𝑛−1≤𝑚≤250000$n-1\le m\le 250000$), the number of nodes and number of wires, respectively.

For the next 𝑚$m$ lines, 𝑖$i$-th line will contains 𝑢𝑖$u_i$, 𝑣𝑖$v_i$ and 𝑤𝑖$w_i$ (1≤𝑢𝑖,𝑣𝑖≤𝑛$1\le u_i,v_i\le n$, 1≤𝑤𝑖≤109$1\le w_i\le {10}^9$) - the indices 2 machines that are connected by the 𝑖$i$-th edge and the weight of it.

It is guaranteed that the sum of 𝑛$n$ over all test cases does not exceed 500$500$ and the sum of 𝑚$m$ over all test cases does not exceed 250000$250000$. The graph in each test case is guaranteed to be connected, no self-loops, but it can contain multiple edges.

Output

For each test case, output one integer denotes the least amount of time needed to transfer the large package from machine 1$1$ to 𝑛$n$.