// Solves problem 4210 from ACM ICPC Live Archive.
// Almost Shortest Path
// Copyright (C) 2011 Santiago Alessandri
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, If not, see .
//
// You can contact me at san.lt.ss@gmail.com
// Visit my wiki at http://wiki.san-ss.com.ar
// Visit my blog at http://blog.san-ss.com.ar
#include
#include
#include
#include
#include
#include
#define INF 99999999
using namespace std;
uint32_t arcs[500 * 500];
uint32_t rarcs[500 * 500];
struct my_pair {
uint16_t u;
uint16_t p;
bool operator<(const my_pair& other) const{
return this->p >= other.p;
}
};
vector dijkstra(uint16_t init, uint16_t size, uint32_t* matrix) {
priority_queue queue;
vector result(size, INF);
bool used[size];
my_pair working, working2;
uint32_t i, dist;
for (i = 0; i < size; ++i)
used[i] = false;
result[init] = 0;
working.u = init;
working.p = 0;
queue.push(working);
while (!queue.empty()) {
working = queue.top();
queue.pop();
if (used[working.u])
continue;
used[working.u] = true;
for (i = 0; i < size; i++) {
dist = matrix[working.u * size + i];
if (result[working.u] + dist < result[i]) {
result[i] = result[working.u] + dist;
working2.u = i;
working2.p = result[i];
queue.push(working2);
}
}
}
return result;
}
int main() {
uint16_t n, m;
uint16_t i, j;
uint16_t s, d;
uint16_t u, v, p;
vector res_d1, res_d2, res_d3;
cin >> n >> m;
while (n != 0) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
arcs[i * n + j] = INF;
rarcs[i * n + j] = INF;
}
}
cin >> s >> d;
for (i = 0; i < m; ++i) {
cin >> u >> v >> p;
arcs[u * n + v] = p;
rarcs[v * n + u] = p;
}
res_d1 = dijkstra(s, n, arcs);
res_d2 = dijkstra(d, n, rarcs);
uint32_t min_path = res_d1[d];
/* Delete arcs that are part of a shortest path */
for (u = 0; u < n; ++u) {
for (v = 0; v < n; ++v) {
uint16_t dist = arcs[u * n + v];
if (res_d1[u] + dist + res_d2[v] == min_path) {
arcs[u * n + v] = INF;
}
}
}
res_d3 = dijkstra(s, n, arcs);
if (res_d3[d] == INF)
cout << -1 << '\n';
else
cout << res_d3[d] << '\n';
cin >> n >> m;
}
return 0;
}