Shortest Path Finder

This problem requires you to compute the shortest path between two attractions in a graph. Each dataset consists of a weighted undirected graph. You are given n attractions (vertices) and m paths (edges). Each path is defined by two attractions and a weight. Your task is to find the shortest path between a specified start and end attraction using Dijkstra's algorithm.

If a path does not exist, output -1.

The shortest distance can be described mathematically by the formula:

\( d(u,v)=\min_{P\in\mathcal{P}(u,v)}\sum_{e\in P} w(e) \)

where \(\mathcal{P}(u,v)\) represents the set of all paths between vertices \(u\) and \(v\), and \(w(e)\) is the weight of edge \(e\).

inputFormat

The input consists of multiple datasets. Each dataset begins with a line containing two integers n and m (1 ≤ n, m). Following this, there are m lines each containing three integers u, v, and w representing an undirected edge between attractions u and v with weight w. The next line contains two integers representing the starting and ending attractions for which you must find the shortest path.

The input is terminated by a line with "0 0".

outputFormat

For each dataset, output a single integer on a new line representing the shortest distance from the start to the end attraction. If no path exists, output -1.

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

6