//      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 <http://www.gnu.org/licenses/>.
//
//      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 <stdint.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>

#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<uint32_t> dijkstra(uint16_t init, uint16_t size, uint32_t* matrix) {
    priority_queue<my_pair> queue;
    vector<uint32_t> 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<uint32_t> 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;
}