#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using pii = pair; using ll = long long; #define rep(i, j) for(int i=0; i < (int)(j); i++) #define repeat(i, j, k) for(int i = (j); i < (int)(k); i++) #define all(v) v.begin(),v.end() #define debug(x) cerr << #x << " : " << x << endl // vector template ostream& operator << (ostream &os , const vector &v) { for(const T &t : v) os << "\t" << t; return os << endl; } template istream& operator >> (istream &is , vector &v) { for(T &a : v) is >> a; return is; } // pair template ostream& operator << (ostream &os , const pair &v) { return os << "<" << v.first << " " << v.second << ">"; } const int INF = 1 << 30; bool solve() { int N, M, S, G; cin >> N >> M >> S >> G; vector> E(N); rep(i, M) { int a, b, c; cin >> a >> b >> c; E[a].push_back(make_pair(b, c)); E[b].push_back(make_pair(a, c)); } priority_queue que; vector dist(N, INF); que.push(make_pair(S, 0)); dist[S] = 0; while(que.size()) { int now = que.top().first; int cost = que.top().second; que.pop(); if(dist[now] < cost) continue; for(pii nxt : E[now]) { int ncost = cost + nxt.second; if(dist[nxt.first] > ncost) { dist[nxt.first] = ncost; que.push(make_pair(nxt.first, ncost)); } } } vector road; int now = G; road.push_back(now); while(now != S) { int prev = INF; for(pii nxt : E[now]) { if(dist[nxt.first] + nxt.second == dist[now]) { prev = min(prev, nxt.first); } } now = prev; road.push_back(now); } reverse(all(road)); rep(i, road.size()) { if(i > 0) cout << " "; cout << road[i]; } cout << endl; return false; } int main() { cin.tie(0); ios::sync_with_stdio(false); while(solve()); return 0; }