Q. You are given a directed weighted graph with n vertices. m pairs of vertices have 2 edges each, ie 2m edges. Each pair of vertex has 2 types of edge:
 1. normal edge
 2. special edge

 You are also given a source S and a destination D. Find the shortest path from S to D using atmost 1 special edge.

 example:
 S=1, D=3
 edge, normal, special
 1->2,   10		9
 2->3,   16 	10
 in this example shortest path is 20 by taking special edge from 2->3

 example 2
 S=1, D=3
 edge, normal, special
 1->2,   10		15
 2->3,   14		15
 ans = 24