Shortest Path in Directed Graph

Given a directed weighted graph with n nodes and m edges, your task is to determine the shortest path distance from a given starting node s to a destination node d. If there is no path from s to d, output NO PATH.

The graph is represented by a series of triples \( (u, v, w) \), where \( u \) is the start node, \( v \) is the end node, and \( w \) is the weight of the edge. You are expected to use Dijkstra's algorithm or any efficient method to solve the problem.

inputFormat

The first line of the input contains four integers: \( n \), \( m \), \( s \) and \( d \), where:

• \( n \) is the number of nodes
• \( m \) is the number of edges
• \( s \) is the starting node
• \( d \) is the destination node

Each of the next \( m \) lines contains three integers \( u \), \( v \), and \( w \) representing a directed edge from node \( u \) to node \( v \) with weight \( w \).

outputFormat

If there is a path from the starting node \( s \) to the destination node \( d \), output the shortest distance as an integer. Otherwise, output NO PATH.

5 6 1 5
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1

6