[5719] 거의 최단경로

// 5719 거의 최단경로  
// 다익스트라  
// 경로 역추적 | 다익스트라 -> 간선 지우기 -> 다익스트라 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

#define MAX_N		500 // 도시 수  
#define MAX_M		10000 // 도로 수  
#define MAX_VALUE  	500500 //
using namespace std;

struct Node{
	int dest; int cost;
	Node(int dest, int cost) : dest(dest), cost(cost){
	}
	// min-heap 
	bool operator<(const Node& a)const{
		return cost > a.cost;
	}
};


int N, M, S, D;

vector<Node> adjList[MAX_N+5];
vector<int> delList[MAX_N+5]; // 이동경로 역추적  

int dist[MAX_N+5];
bool visited[MAX_N+5];

void dijkstra(int start){
	priority_queue<Node> PQ;
	
	dist[start] = 0;
	PQ.push(Node(start, 0));
	
	while(!PQ.empty()){
		Node now = PQ.top();
	
		PQ.pop();
		if(dist[now.dest] < now.cost) continue;
		
		// 연결된 간선 탐색  
		for(Node next: adjList[now.dest]){
			// 최단거리로 지워진 간선은 건너뛴다. 
			if(next.cost == -1) continue; 
			
			// cost가 더 작을 때만 갱신하고 우선순위 큐에 넣는다.  
			if(dist[next.dest] > next.cost + now.cost){ // 방문 안했으면 MAX로 초기화 했으므로  
				dist[next.dest] = next.cost + now.cost;
				PQ.push(Node(next.dest, dist[next.dest]));
				// 새로운 최단거리를 발견했으므로, 이전 것 초기화 
				delList[next.dest].clear();
				// 새로운 최단거리 노드를 넣는다.
				delList[next.dest].push_back(now.dest);
 
			} 
			// 같은 비용이라면, 최소거리 경로가 여러 개  
			else if(dist[next.dest] == next.cost + now.cost){
				delList[next.dest].push_back(now.dest);
			}
		}
	}
} 

void del_bfs(int start){
	queue<int> Q;
	Q.push(start);
	
	while(!Q.empty()){
		int now = Q.front();
		Q.pop();
		
		if(visited[now] != 0) continue;
		visited[now] = 1;
		
		for(int i=0; i<delList[now].size(); i++){
			int next = delList[now][i];
			
			for(int j=0; j<adjList[next].size(); j++){
				if(adjList[next][j].dest == now){
					adjList[next][j].cost = -1;
				}
			}
			Q.push(next);
		}
	}
}

// 다익스트라
// 간선을 지우고 -> 지운 간선 정보  
// 다시 다익스트라  

int main(){
	
	while(1){
		// N = 장소 수 2 ~ 500 
		// M = 도로 수 1 ~ 1000 
	    scanf("%d %d", &N, &M);
	    
	    if(N==0 && M==0) break;
	    
	    // S = 시작점 D = 도착점  
	    scanf("%d %d", &S, &D); 
	    
	     // 인접리스트 초기화  
	    for(int i=0; i<N+1; i++){
	    	adjList[i].clear();
	    	delList[i].clear();
	    	dist[i] = MAX_VALUE;
	    	visited[i] = 0;
		}
	    
	    // 간선 삽입  
	    for(int i=0; i<M; i++){
	    	int U, V, P;
	    	scanf("%d %d %d", &U, &V, &P); 
	    	adjList[U].push_back(Node(V, P));
		}
	    
	    dijkstra(S); // 최단거리 찾기  
	    
	    del_bfs(D); // 최단거리가 지나는 간선 삭제  
	    
	    // 초기화 & 다시 다익스트라  
	    for(int i=0; i<N+1; i++){
	    	dist[i] = MAX_VALUE;
		} 
		dijkstra(S);
		
		if(dist[D] == MAX_VALUE){
			printf("-1\n");
		} 
		else{
			printf("%d\n", dist[D]);
		}	
	}   
}