Shortest Path in an Undirected Weighted Graph

You are given an undirected weighted graph with n nodes and m edges. Your task is to find the shortest path between two given nodes using Dijkstra's algorithm.

The first line of input contains two integers n and m. Each of the next m lines contains three integers u, v, and w representing an edge between nodes u and v with weight w. The last line contains two integers s and t, the source and target nodes respectively.

If there is a path between s and t, output the length of the shortest path. Otherwise, print Infinity.

Note: Use Dijkstra's algorithm where the update formula is given by: $$d[v] = \min\{d[v],\,d[u] + w(u,v)\},$$ where \(w(u,v)\) denotes the weight of the edge from \(u\) to \(v\).

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers n and m (the number of nodes and edges respectively).
• Each of the next m lines contains three integers u, v, and w representing an undirected edge from node u to node v with weight w.
• The last line contains two integers s and t, representing the source and target nodes.

outputFormat

Output the length of the shortest path from node s to node t to standard output (stdout). If there is no such path, output Infinity.

4 4
1 2 24
1 4 20
3 1 3
4 3 12
1 4

15