NINJA6  TRAVELLING DILEMMA
Problem statement:
A graph of a country is given. There are N cities and M number of roads. Each road connect two cities. Now you are given two modes of traveling from one city to another.
> By using public transportation.
> By using your own car.(which you can use only once between any two cities on your way). You may or maynot use this mode of travel.
The country's map is given as a graph with N nodes (labeled from 1 to N), and the initial station is node S and the destination is node D. There are two undirected edges between each of the given nodes:
> one denotes the cost of a path using public transportation, r.
> and the other denotes the cost of a path using your own car, t.
Now you have to find the most optimal way (in terms of time of cost) from S to D with or without using your entitled car ride. Output the minimized cost of your travel from the source to the destination.
Input:
The first line contains T, the number of test cases.
For each test case:
The first line contains two spaceseparated integers, N (the number of cities in the map) and M (the number of roads in the map), respectively.
The next M lines each have four space separated integers c1, c2, r, and t, respectively; c1 and c2 denote two cities connected by a road, r is the cost for using the public transportation, and t is the cost of taking your own car on the road.
The last line has two spaceseparated integers, S (Starting city) and D (Destination), respectively.
Constraints:
1 ≤ T ≤ 10
2 ≤ N ≤ 3000
1 ≤ M≤ N×(N−1)
1 ≤ x, y, S,D ≤ N
1 ≤ r, t ≤ 500
Output:
For each test case, print a single line with minimum travel cost. If the destination (D) is unreachable from the source node (S), print −1.
Sample input:
1
4 5
1 2 6 5
1 3 4 5
2 3 6 1
2 4 3 4
3 4 5 7
1 4
Sample output:
8
hide comments
levim:
20170318 20:14:07
@shivucoder55, The car can only be used once from source to destination 

shivucoder55:
20160310 13:40:51
From Source to destination , only 1 time car can be used or we can use more than once but between each pair of cities connected via given roads only 1 time car can be used ? .... Thanks for help in advance 
Added by:  mombassa 
Date:  20160217 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 