Please give me some ideas to solve this problem, I tried to use Floyd Warshell to solve it but I was confused on how to set up a VIP card to set a path as 0 to get the shortest path from 1 to N.

If you can write some code for me, please write in C language thanks.

There are N cities and M bidirectional roads. The i-th road connects city A; and city B;, and the cost of passing it is C. You have a VIP card, that can let you go through any road for free. The VIP card can be used only once. Your objective is to travel from city 1 to city N. Find the minimum possible total cost. I/O Format Use standard I/O. (stdin, stdout) Input There is only one test case per input file. The first line contains two integers N and M. The i-th of the next M lines contains three integers A;, B; and C each. (1 S A, B, 2->3->4->6, and use the VIP card when going through the road connecting city 3 and city 4. The total cost is 1+1+10=12. Input 3: You should follow the path 1->7->8->10, and use the VIP card when going through the road connecting city 1 and city 7. The total cost is 16+33=49