#include <bits/stdc++.h>
using namespace std;

int T, n, m, s, t, a, b, c, cnt = 0;
struct Edge {
	int nxt, to, w;
} edge[200001];

int head[100001], dist[100001];
bool vis[100001];

void create(int u, int v, int w) {
	cnt++;
	edge[cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}

void dijkstra(int start) {    
	priority_queue<pair<int, int>> q;
	memset(dist, 0x3f3f3f3f, sizeof dist);
	memset(vis, 0, sizeof vis);
	
	dist[start] = 0;
	q.push(make_pair(0, start));
	
	while (!q.empty()) {
		int cur = q.top().second;
		q.pop();

		if (vis[cur]) continue;
		vis[cur] = true;
		
		for (int i = head[cur]; i; i = edge[i].nxt) {
			int y = edge[i].to;
			int new_dist = dist[cur] + edge[i].w;
			
			if (!vis[y] && new_dist < dist[y]) {
				dist[y] = new_dist;
				q.push(make_pair(-dist[y], y));
			}
		}
	}    
}

void DIJKSTRA() {
	memset(head, 0, sizeof head);
	cnt = 0;
	
	cin >> n >> m >> s >> t;
	for (int i = 1; i <= m; i++) {
		cin >> a >> b >> c;
		create(a, b, c);
		create(b, a, c);
	}
	
	dijkstra(s);
	cout << dist[t];    
}

int main() {
	T = 1;
	while (T--) {
		DIJKSTRA();    
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n, m, c1, c2;
int dist[251][251];

void floyd() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (dist[i][k] != 0x3f3f3f3f && dist[k][j] != 0x3f3f3f3f) {
					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}
	}
}

void FLOYD() {
	cin >> n >> m;

	memset(dist, 0x3f3f3f3f, sizeof dist);
	for (int i = 1; i <= n; i++) {
		dist[i][i] = 0;
	}

	for (int i = 1; i <= m; i++) {
		cin >> c1 >> c2;
		dist[c1][c2] = 1;
		dist[c2][c1] = 1;
	}
	
	floyd();
}

int main() {
	int T = 1;
	while (T--) {
		FLOYD();
	}
	
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int t, n, m, u, v, w, edge_cnt;
struct Edge {
	int nxt, to, w;
} edge[200001];

int head[100001], dist[100001], inq_count[100001];
bool in_queue[100001];

void create(int u, int v, int w) {
	edge_cnt++;
	edge[edge_cnt].to = v;
	edge[edge_cnt].w = w;
	edge[edge_cnt].nxt = head[u];
	head[u] = edge_cnt;
}

queue<int> q;
inline bool spfa(int s) {
	memset(dist, 0x3f, sizeof dist);
	memset(inq_count, 0, sizeof inq_count);
	memset(in_queue, 0, sizeof in_queue);
	
	while (!q.empty()) q.pop();
	
	dist[s] = 0;
	in_queue[s] = true;
	inq_count[s] = 1;
	q.push(s);
	
	while (!q.empty()) {
		int x = q.front();
		in_queue[x] = false;
		q.pop();
		
		for (int i = head[x]; i; i = edge[i].nxt) {
			int y = edge[i].to;
			if (dist[x] + edge[i].w < dist[y]) {
				dist[y] = dist[x] + edge[i].w;
				
				if (!in_queue[y]) {
					inq_count[y]++;
					if (inq_count[y] >= n) {
						cout << "存在负环" << endl;
						return 1;
					}
					in_queue[y] = true;
					q.push(y);
				}
			}
		}
	}
	
	return 0;
}

int main() {
	cin >> t;
	while (t--) {
		memset(head, 0, sizeof head);
		edge_cnt = 0;
		
		cin >> n >> m;
		for (int i = 1; i <= m; i++) {
			cin >> u >> v >> w;
			create(u, v, w);
			// create(v, u, w);
		}
		
		spfa(1);
	}
	
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n, m, u, v, in[100001];
vector<int> G[100001];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> u >> v;
		G[u].push_back(v);
		in[v]++;
	}
	
	vector<int> L;
	queue<int> S;

	for (int i = 0; i < n; i++) {
		if (in[i] == 0) {
			S.push(i);
		}
	}
	
	while (!S.empty()) {
		int u = S.front();
		S.pop();
		L.push_back(u);
		
		for (auto v : G[u]) {
			if (--in[v] == 0) {
				S.push(v);
			}
		}
	}
	
	for (auto i : L) {
		cout << i << " ";
	}
	
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
		
int n, m, p, father[5001];
		
int find(int x) {
	if (father[x] == x)
		return x;
	
	return father[x] = find(father[x]);	
}
		
void merge(int x, int y) {
	int a = find(x), b = find(y);
	if (a != b)
		father[a] = b;
}
		
int main() {
	for (int i = 1;i <= n;i ++)
		father[i] = i;
		
	return 0;
}