#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 5e3 + 5;
const int M = 2e5 + 5;
struct Edge {
int to;
int next;
int w;
} edge[M << 1];
int head[N], ecnt;
void addEdge(int u, int v, int w) {
edge[++ecnt] = {v, head[u], w};
head[u] = ecnt;
}
int dis[N];
int inq[N];
int cnt[N];
int vis[N];
int n;
void bellmanford(int n, int s) {
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
for (int k = 1; k < n; k++) {
bool flag = 0;
for (int u = 1; u <= n; u++) {
for (int i = head[u]; i != 0; i = edge[i].next) {
int v = edge[i].next;
int w = edge[i].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
flag = 1;
}
}
}
if (flag == 0) break;
}
}
int spfa(int s) {
queue<int> qu;
dis[s] = 0;
qu.push(s);
inq[s] = 1;
cnt[s] = 1;
while (!qu.empty()) {
int u = qu.front();
qu.pop();
inq[u] = 0;
for (int i = head[u]; i != 0; i = edge[i].next) {
int v = edge[i].to;
int w = edge[i].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!inq[v]) {
qu.push(v);
cnt[v]++;
inq[v] = 1;
if (cnt[v] > n) {
return -1;
}
}
}
}
}
return 1;
}
struct Node {
int v;
int w;
bool operator < (Node b) const {
return w > b.w;
}
};
void dijkstra(int s) {
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
priority_queue<Node> qu;
qu.push({s, 0});
while (!qu.empty()) {
Node now = qu.top();
qu.pop();
int u = now.v;
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; i != 0; i = edge[i].next) {
int v = edge[i].to;
int w = edge[i].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (vis[v]) continue;
qu.push({v, dis[v]});
}
}
}
}
int main(void)
{
return 0;
}