irctc

Good news , You have a chance to work in IRCTC as a software developer . Applications are required with a program for railway sites . sid of a station is a  something which uniquely defines it . Given N station's sid from 1 to N and distance between any two stations , if any person wants to go from station having sid A to another station C via station B as early as possible  , where time is directly proportional to distance .  What you have to do is to print the total distance and path to be covered by train if it  exists , otherwise print "No Train Found.". If a railway line connects station A to B with distance d than it means it will also connects station B to station A with same distance d .

Input
First line of the input contains the number of test cases T. It is followed by T tests cases.  Each test case's  first line contains two integers N and k , where N is the number of stations having sid from 1 to N and k is the number of railway lines which connects stations.  Following k lines each contain three numbers  a , b and d which represents station having sid a connects station b and distance between them is d . After that a line follows with number A , B , C , where A represents sid of  the source station , C  the destination station and B is the station via which  person wants to go.

Output
For each test case , If there  exists no paths as described in problem print "No Train Found." otherwise in first line print the total distance and in second line path to be covered .

Constraints
1 ≤ t ≤ 100
1 ≤ k ≤ 100000
3 ≤ N ≤ 100000
1 ≤ A,B,C ≤ N
1 ≤ d ≤ 10000000

SAMPLE INPUT
2
6 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
1 3 6
10 10
1 5 78
1 8 221
2 7 92
2 8 159
3 5 55
3 6 179
3 10 237
4 8 205
5 6 191
8 10 157
6 3 2

SAMPLE OUTPUT
No Train Found.
692
6 3 5 1 8 2

Source: hackerearth | Difficulty: MEDIUM
Tags: Fundamentals


Solutions:
import heapq
INF = 1 + 25 * 10**9
def dijkstra(G, n, s,de):
	dist = [INF] * (n+1)
	#path=[]
	dist[s] = 0
	heap = []
	heapq.heappush(heap, (0,s))

	while heap:
		d, u = heapq.heappop(heap)
		if dist[u] < d:
			continue
		#path.append(u)    
		if u==de:
			break    
		
		for (v, w) in G[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				heapq.heappush(heap, (dist[v], v))#negative cycles would lead to infinite loop here.
				parent[v]=u
				#path.append(v)

	return dist
def trail(i,j):
	t=[]
	global parent
	found=False
	while not found:
		#print i,j
		t.append(i)
		i=parent[i]
		if i==j:
			found=True
			t.append(i)
	t.reverse()          
	return t 
def p(y):
	for i in y:
		print(i, end=' ')
	print("\r")        
t=eval(input())
while t!=0:
 n, m = list(map(int, input().split()))
 G = [[] for i in range(n+1)]
 parent=[0] * (n+1)

 for i in range(m):
	x, y, z = list(map(int, input().split()))
	G[x].append((y, z))
	G[y].append((x, z))
 s,v,d=list(map(int, input().split()))   

 distStart = dijkstra(G, n, s,v)
 #print parent,distStart
 if distStart[v]!=INF:
  a1=trail(v,s)
 
 #print distStart
 distend=dijkstra(G,n,v,d)
 if distend[d]!=INF:
   b1= trail(d,v)
 if distStart[v]!=INF and distend[d]!=INF:
	 print(distStart[v]+ distend[d])
	 #print parent,distend
	 p (a1+b1[1::])
 else:
	 print("No Train Found.")    
  
 
 t-=1