Cod sursa(job #712116)
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
struct edge{int v, d;};
int n, m, x, y, d[30000];
vector <edge> G[30000];
queue <int> q;
int main(){
freopen("sate.in", "r", stdin), freopen("sate.out", "w", stdout);
scanf("%d %d %d %d", &n, &m, &x, &y);
int i, a, b, l;
for (i = 0; i < m; i++)
scanf ("%d %d %d", &a, &b, &l),
G[a].push_back((edge) {b, l}),
G[b].push_back((edge) {a, -l});
q.push(x);
memset(d, -1, (n + 1) * sizeof(int));
d[x] = 0;
while (!q.empty()){
a = q.front(), q.pop();
for (i = 0; i < G[a].size(); i++){
b = G[a][i].v;
if (d[b] == -1) q.push(b);
d[b] = d[a] + G[a][i].d;
}
}
printf("%d", d[y]);
}