Taco Graph Shortest Path

You are given a directed weighted graph with N nodes and M edges. The nodes are numbered from 1 to N. Each edge is described by three integers u, v, and w, which means there is a directed edge from node u to node v with weight w (where w is a non-negative integer).

Your task is to compute the shortest path from a given starting node S to an ending node E. If there is no path from S to E, output -1.

The problem is formally defined with the following constraints:

• $2 \le N \le 10^5$
• $1 \le M \le 10^6$
• $1 \le S, E \le N$
• $0 \le w \le 100$ for each edge weight

This is a classic application for Dijkstra's algorithm. Good luck!

inputFormat

The first line contains four space-separated integers: N, M, S, and E, representing the number of nodes, the number of edges, the starting node, and the ending node respectively.

The following M lines each contain three space-separated integers u, v, and w, representing a directed edge from node u to node v with weight w.

outputFormat

Output a single integer, which is the minimum weight of the shortest path from node S to node E. If there is no valid path, output -1.

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

4