Minimum Transfer Time

You are given a network of n computers and m bidirectional connections between them. Each connection has an associated transfer time. Given two specific computers, a starting computer and a target computer, your task is to compute the minimum transfer time required to send data from the starting computer to the target computer.

If there is no possible route between the two computers, output \( -1 \). Otherwise, output the minimum transfer time. The transfer time along a path is the sum of the weights of the edges along that path.

Note: Use Dijkstra's algorithm (or any other suitable shortest path algorithm) to solve this problem efficiently. The formula for the distance update is given by \( d(v)=\min(d(v), d(u)+w(u,v)) \), where \( w(u,v) \) is the weight of the edge between nodes \( u \) and \( v \).

inputFormat

The first line contains four integers \( n \), \( m \), \( start \), and \( end \), where \( n \) is the number of computers, \( m \) is the number of connections, \( start \) is the starting computer index, and \( end \) is the target computer index.

The next \( m \) lines each contain three integers \( u \), \( v \), and \( w \), representing a bidirectional connection between computer \( u \) and computer \( v \) with transfer time \( w \).

It is guaranteed that the indices of the computers are from 1 to \( n \).

outputFormat

Output a single integer representing the minimum transfer time from the starting computer to the target computer. If there is no valid path, output \( -1 \).

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

6