1#include<bits/stdc++.h>
2#include<iostream>
3using namespace std;
4using ll = long long;
5
6const int maxN = 100001;
7const int INF = 1e9; // so vo cung
8
9int n, m; // n: so dinh, m: so canh
10int s; // dinh bat dau
11int t; // dinh ket thuc
12vector<pair<int, int>> adj[maxN]; // vector luu tru canh co trong so
13int parent[maxN]; // mang dung de tracking duong di
14
15void inp() {
16 cin >> n >> m >> s >> t;
17 for(int i = 0; i < m; i++) {
18 int x, y, w; // canh x -> y co trong so w
19 cin >> x >> y >> w;
20 adj[x].push_back({y, w});
21
22 // Do thi co huong thi comment dong code sau
23 //adj[y].push_back({x, w});
24 }
25}
26
27void dijkstra(int s, int t) {
28 // Mang luu khoang cach duong di
29 vector<ll> d(n+1, INF);
30 d[s] = 0;
31 parent[s] = s;
32
33 // Hang doi uu tien
34 // {khoang_cach, dinh}
35 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
36 Q.push({0, s}); // Khoi tao
37 while(!Q.empty()) {
38 // Chon ra dinh co khoang cach tu s nho nhat
39 pair<int, int> top = Q.top();
40 Q.pop();
41
42 int u = top.second;
43 int kc = top.first;
44 if(kc > d[u])
45 continue;
46
47 // Relaxation: cap nhat khoang cach tu s cho toi moi dinh ke voi u
48 for(auto it: adj[u]) {
49 int v = it.first;
50 int w = it.second;
51 if(d[v] > d[u] + w) {
52 d[v] = d[u] + w;
53 Q.push({d[v], v});
54
55 parent[v] = u; // truoc v la u
56 }
57 }
58 }
59
60 cout << d[t] << endl;
61 vector<int> path;
62 while(1) {
63 path.push_back(t);
64 if(t == s)
65 break;
66
67 t = parent[t];
68 }
69 reverse(begin(path), end(path));
70 for(int x: path) {
71 cout << x << " ";
72 }
73}
74
75int main() {
76 // Chuyen NHAP, XUAT thanh file
77 freopen("lab_5_1_input.INP", "r", stdin);
78 freopen("lab_5_1_output.OUT", "w", stdout);
79
80 // INPUT
81 inp();
82
83 // OUTPUT
84 dijkstra(s, t);
85}