//sate
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int MAXN = 30005;

vector<pair<int, int>> g[MAXN];
int viz[MAXN];
long long d[MAXN];

void dfs(int nod, long long dist_curenta) {
    viz[nod] = 1;
    d[nod] = dist_curenta;
    for (size_t i = 0; i < g[nod].size(); ++i) {
        int vecin = g[nod][i].first;
        int dist = g[nod][i].second;
        if (!viz[vecin]) {
            dfs(vecin, dist_curenta + dist);
        }
    }
}

int main() {
    ifstream fin("sate.in");
    int n, m, x, y;
    if (!(fin >> n >> m >> x >> y)) return 0;

    for (int k = 0; k < m; ++k) {
        int i, j, dist;
        fin >> i >> j >> dist;
        g[i].push_back({j, dist});
        g[j].push_back({i, -dist});
    }
    fin.close();

    dfs(x, 0);

    ofstream fout("sate.out");
    fout << d[y] << "\n";
    fout.close();

    return 0;
}








/*
//Drumuri
#include <stdio.h>
#include <vector>
using namespace std;

#define Nmax 10001
#define Mmax 30001

int N,M,i;
int x[Mmax],y[Mmax];
int was[Nmax],grad[Nmax];
vector<int> G[Nmax];

int citire()
{
 freopen("drumuri.in","r",stdin);
 scanf("%d %d",&N,&M);
 if (M & 1) return 0;
 for (i=1;i<=M;++i)
     {
      scanf("%d %d",&x[i],&y[i]);
      G[x[i]].push_back(i);
      G[y[i]].push_back(i);
      ++grad[x[i]];
      ++grad[y[i]];
     }
 return 1;
}

void dfs(int nod,int stra)
{
 vector<int>::iterator it;
 int nr=1;
 was[nod]=1;
//parcurgere
 for (it=G[nod].begin();it<G[nod].end();++it)
     if ( (x[*it]!=nod) && (!was[x[*it]] ) )
         dfs(x[*it],nod);
       else
     if ( (y[*it]!=nod) && (!was[y[*it]] ) )
         dfs(y[*it],nod);
 if ((grad[nod] & 1) == 0)
    for (it=G[nod].begin();it<G[nod].end();++it)
        if (x[*it]==nod)
           {
            if ((nr^=1)==0) printf("%d %d",y[*it],x[*it]);
              else printf(" %d\n",y[*it]);
            --grad[x[*it]];
            --grad[y[*it]];
            x[*it]=y[*it]=0;
           }
         else if (y[*it]==nod)
          {
           if ((nr^=1)==0) printf("%d %d",x[*it],y[*it]);
              else printf(" %d\n",x[*it]);
           --grad[x[*it]];
           --grad[y[*it]];
           x[*it]=y[*it]=0;
          }
          else ;
  else
    for (it=G[nod].begin();it<G[nod].end();++it)
        if ((x[*it]==nod) && (y[*it]!=stra))
           {
            if ((nr^=1)==0) printf("%d %d",y[*it],x[*it]);
              else printf(" %d\n",y[*it]);
            --grad[x[*it]];
            --grad[y[*it]];
            x[*it]=y[*it]=0;
           }
         else if ((y[*it]==nod) && (x[*it]!=stra))
          {
           if ((nr^=1)==0) printf("%d %d",x[*it],y[*it]);
              else printf(" %d\n",x[*it]);
           --grad[x[*it]];
           --grad[y[*it]];
           x[*it]=y[*it]=0;
          }
}

int main()
{
 freopen("drumuri.out","w",stdout);
 was[0]=1;
 if (citire()) {
                 printf("%d\n",1);
                 dfs(1,0);
               }
    else printf("%d",0);
 fclose(stdout);
 fclose(stdin);
 return 0;
}
*/














/*
//Dep
#include <cstdio>
#include <vector>
#include <algorithm>

#define MOD 666013

#define MAXN 256

std::vector <int> g1[MAXN+1], g2[MAXN+1], v1[MAXN+1], v2[MAXN+1];

int ans;

int u, w, k, r[MAXN+1], s[MAXN+1], c[MAXN+1], best[MAXN+1], h[MAXN+1], t[MAXN+1];
bool e[MAXN+1], viz[MAXN+1], m1[MAXN+1][MAXN+1], m2[MAXN+1][MAXN+1];
int dp[MAXN+1][MAXN+1], aux[MAXN+1];

void dfs1(int x){
    viz[x]=1;
    for(auto y:g1[x])
        if(viz[y]==0)
            dfs1(y);
    r[++u]=x;
}

void dfs2(int x){
    viz[x]=0;
    s[k]++;
    c[x]=k;
    for(auto y:g2[x])
        if(viz[y]==1)
            dfs2(y);
}

void dfs3(int x){
    viz[x]=1;

    dp[x][s[x]]=1;

    for(auto y:v1[x]){
        if(viz[y]==0){
            h[y]=h[x]+1;
            t[y]=x;
            dfs3(y);
            for(int i=0; i<=w; i++){
                aux[i]=dp[x][i];
                dp[x][i]=0;
            }

            for(int i=0; i<=w; i++)
                for(int j=0; i+j<=w; j++)
                    dp[x][i+j]=(dp[x][i+j]+1LL*aux[i]*dp[y][j])%MOD;
        }
    }

    dp[x][0]=1;
}

int main(){
    FILE *fin, *fout;
    fin=fopen("dep.in", "r");
    fout=fopen("dep.out", "w");

    int n, m;
    fscanf(fin, "%d%d%d", &n, &m, &w);

    for(int i=1; i<=m; i++){
        int x, y;
        fscanf(fin, "%d%d", &x, &y);

        g1[y].push_back(x);
        g2[x].push_back(y);
    }

    for(int i=1; i<=n; i++)
        if(viz[i]==0)
            dfs1(i);

    for(int i=n; i>0; i--){
        if(viz[r[i]]==1){
            k++;
            dfs2(r[i]);
        }
    }

    for(int i=1; i<=n; i++){
        m1[c[i]][c[i]]=1;
        for(auto x:g1[i]){
            if(m1[c[i]][c[x]]==0){
                m1[c[i]][c[x]]=1;
                v1[c[i]].push_back(c[x]);
            }
        }

        m2[c[i]][c[i]]=1;
        for(auto x:g2[i]){
            if(m2[c[i]][c[x]]==0){
                m2[c[i]][c[x]]=1;
                v2[c[i]].push_back(c[x]);
            }
        }
    }

    for(int i=1; i<=k; i++)
        std::sort(v1[i].begin(), v1[i].end());

    for(int i=1; i<=k; i++){
        if(viz[i]==0){
            dfs3(i);
            v1[0].push_back(i);
        }
    }

    int x=0;

    dp[0][0]=1;
    for(auto y:v1[0]){
        for(int i=0; i<=w; i++){
            aux[i]=dp[x][i];
            dp[x][i]=0;
        }
        for(int i=0; i<=w; i++)
            for(int j=0; i+j<=w; j++)
                dp[x][i+j]=(dp[x][i+j]+1LL*aux[i]*dp[y][j])%MOD;
    }

    fprintf(fout, "%d\n", dp[0][w]);

    fclose(fin);
    fclose(fout);
    return 0;
}
*/






//Pamant
/*
#include <fstream>

using namespace std;

ifstream f("pamant.in");
ofstream g("pamant.out");

int n,m,L[400004],urm[400004],vec[400004],k,nr,cc[100004],low[100004],lev[100004],np,rad,nf[100004];
bool viz[100004],pa[100004];

void Add(int x1, int x2)
{
    urm[++k]=L[x1];
    vec[k]=x2;
    L[x1]=k;
}

void DFS(int nc, int t)
{
    int z,nn;
    viz[nc]=1;
    lev[nc]=lev[t]+1;
    low[nc]=lev[nc];
    z=L[nc];
    while (z)
    {
        nn=vec[z];
        if (nn!=t)
        {
            if (!viz[nn])
            {
                nf[nc]++;
                DFS(nn,nc);
                low[nc]=min(low[nc],low[nn]);
                if (low[nn]>=lev[nc] and nc!=rad)
                    pa[nc]=1;
            }
            else
                low[nc]=min(low[nc],lev[nn]);
        }
        z=urm[z];
    }
}

int main()
{
    int i,x1,x2;
    f >> n >> m;
    for (i=1;i<=m;i++)
    {
        f >> x1 >> x2;
        Add(x1,x2);
        Add(x2,x1);
    }
    for (i=1;i<=n;i++)
        if (!viz[i])
        {
            rad=i;
            DFS(i,0);
            if (nf[i]>=2)
                pa[i]=1;
            cc[++nr]=i;
        }
    for (i=1;i<=n;i++)
        np+=pa[i];
    g << nr << '\n';
    for (i=1;i<=nr;i++)
        g << cc[i] << ' ';
    g << '\n' << np << '\n';
    for (i=1;i<=n;i++)
        if (pa[i])
            g << i << ' ';
    return 0;
}
*/




//Ctc
/*
#include <iostream>
#include <vector>
#include <fstream>
#define NMAX 100001

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, nr, nrc;

//graful initial prin liste de adiacenta
 vector<int> G[NMAX];

//graful transpus
 vector<int> GT[NMAX];

 int post[NMAX];
 bool viz[NMAX];

 vector<int> ctc[NMAX]; //contine vf din comp tare conexa i

 void DFS(int x);
 void DFST(int x);

 void citire();
 void afisare();

 void citire()
 {
    int m, i, x, y;
    fin >> n >> m;
    for(int i=0; i<m; i++)
    {
        fin >> x >> y;
        //exista arc de la x la y in G
        G[x].push_back(y);
        //exista arc de la y la x in GT
        GT[y].push_back(x);
    }
 }

 void afisare()
 {
     fout << nrc << " " << endl;
     for(int i=1; i<=nrc; i++)
     //afisaz vf din comp tacre conexa i
     {
         for(int j=0; j<ctc[i].size(); j++)
            fout << ctc[i][j] << " ";
            fout << endl;
     }
        fout << endl;
 }

 void DFS(int x)
 {
     int i;
     viz[x]=1;
     for(i=0; i<G[x].size(); i++)
        if(!viz[G[x][i]])
            DFS(G[x][i]);
    post[++nr]=x;
 }

  void DFST(int x)
 {
     int i;
     viz[x]=0;
     ctc[nrc].push_back(x);
     for(i=0; i<GT[x].size(); i++)
        if(viz[GT[x][i]])
            DFST(GT[x][i]);
 }

int main()
{
    citire();
    for(int i=1; i<=n; i++)
        if(!viz[i])
        DFS(i);
    //parcurg vec post de la dr la st
    for(int i=n; i>0; i--)
        if(viz[post[i]]==1) //post de i nevizitat in GT
            {
                //am identificat o comp noua tare conexa
                nrc++;
                DFST(post[i]);
            }
    afisare();
    return 0;
}
*/




//Biconex
/*
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int n, m, nrcomp;
vector<int> gf[100001];
vector<pair<int, int>> muchii;
vector<vector<int>> comp;
int viz[100001], nivel[100001], nma[100001], ptart[100001];
stack<int> s;

void DFS_biconex(int k, int tata, int rad) {
    viz[k] = 1;
    nivel[k] = nivel[tata] + 1;
    nma[k] = nivel[k];
    s.push(k);
    int nrfii = 0;
    for (int x : gf[k])
        if (x != tata)
            if (!viz[x]) {
                nrfii++;
                DFS_biconex(x, k, rad);
                nma[k] = min(nma[k], nma[x]);

                // determinare puncte de articulație
                if (nivel[k] <= nma[x] && k != rad)
                    ptart[k] = 1;
                // determinare punți
                if (nivel[k] < nma[x])
                    muchii.push_back({ k, x });
                // determinare componente biconexe
                if (nivel[k] <= nma[x]) {
                    nrcomp++;
                    comp.push_back(vector<int>(0));
                    while (s.top() != x) {
                        comp[nrcomp - 1].push_back(s.top());
                        s.pop();
                    }
                    comp[nrcomp - 1].push_back(s.top());
                    s.pop();
                    comp[nrcomp - 1].push_back(k);
                }
            }
            else
                nma[k] = min(nma[k], nivel[x]);
    if (k == rad && nrfii > 1)
        ptart[k] = 1;
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        gf[x].push_back(y);
        gf[y].push_back(x);
    }
    DFS_biconex(1, 0, 1);
    fout << nrcomp << "\n";
    for (int i = 0; i < nrcomp; i++) {
        for ( int j : comp[i])
            fout << j << " ";
        fout << "\n";
    }
    return 0;
}
*/





/*
//Easygraph
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<climits>
using namespace std;
int m,n,i,k,cost[15005],x,y,a,b,t,grad[15005];
vector<int>v[15005];
long long dp[15005],rez;
bool viz[15005];

void df(int x)
{
    viz[x]=true;
    for (int j=0;j<v[x].size();j++)
        {
            if (!viz[v[x][j]]) df(v[x][j]);
            dp[x]=max(dp[x],dp[v[x][j]]+cost[x]);
        }
    rez=max(rez,dp[x]);
}

int main()
{
    freopen("easygraph.in","r",stdin);
    freopen("easygraph.out","w",stdout);
    scanf("%d",&t);
    for (;t>=1;t--)
    {
        for(i=1;i<=n;i++) v[i].clear();
        rez=LONG_MIN;
        memset(grad,0,sizeof(grad));
        memset(viz,false,sizeof(viz));
        fill(dp,dp+15000+1,LONG_MIN);
        scanf("%d %d",&n,&m);
        for (i=1;i<=n;i++) scanf("%d",&cost[i]),dp[i]=cost[i];
        for (i=1;i<=m;i++)
            scanf("%d %d",&x,&y),v[x].push_back(y),grad[y]++;
        for (i=1;i<=n;i++)
            if (!grad[i])
                df(i);
        printf("%lld\n",rez);
    }
    return 0;
}
*/






/*
//Path
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

#define mp make_pair
#define pb push_back

#define maxN 61

int n, m, k, i;
vector<int> list[maxN];
bool valid[maxN];
char c1, c2;

int deep[maxN];
int how[maxN];
int gr[maxN];
queue<int> Q;

vector<int> rev[maxN];
int now_deep, now_node;

int get_id(char c) {
    if ('a' <= c && c <= 'z')
        return c - 'a' + 1;
    else
        return c - 'A' + 26 + 1;
}

char get_char(char c) {
    if (c > 26)
        return 'A' + c - 26 - 1;
    else
        return 'a' + c - 1;
}

int main()
{
    freopen("path.in","r",stdin);
    freopen("path.out","w",stdout);

    scanf("%d%d%d\n", &n, &m, &k);
    n = 52;

    for (i = 1; i <= m; i++) {
        scanf("%c %c\n", &c1, &c2);

        int id1 = get_id(c1);
        int id2 = get_id(c2);

        valid[id1] = valid[id2] = true;
        list[id1].pb(id2);

        gr[id1]++;
        rev[id2].pb(id1);
    }

    for (i = 1; i <= n; i++) {
        if (valid[i] && gr[i] == 0) {
            Q.push(i);
            deep[i] = 1;
            how[i] = 1;
        }
    }

    while (!Q.empty()) {
        int node = Q.front(); Q.pop();

        for (auto to : rev[node]) {
            if (--gr[to] == 0)  Q.push(to);

            if (deep[to] > deep[node] + 1) continue;
            if (deep[to] == deep[node] + 1) how[to] += how[node];
            if (deep[to] < deep[node] + 1) {
                deep[to] = deep[node] + 1;
                how[to] = how[node];
            }
        }

        now_deep = max(now_deep, deep[node]);
    }

    for (i = 1; i <= n; i++)
        if (valid[i])
            list[0].pb(i);


    now_node = 0;
    for (int max_deep = now_deep; max_deep > 0; max_deep--) {
        for (int i = 0; i < list[now_node].size(); i++) {
            int to = list[now_node][i];

            if (deep[to] != now_deep) {
                list[now_node][i] = list[now_node][ list[now_node].size() - 1 ];
                list[now_node].pop_back();
                i--;
            }
        }

        sort(list[now_node].begin(), list[now_node].end());
        for (auto to : list[now_node]) {
            if (how[to] < k) {
                k -= how[to];
                now_node = to;
            } else {
                now_node = to;
                now_deep--;
                break;
            }
        }

        printf("%c", get_char(now_node));
    }


    return 0;
}
*/





/*
//alice2
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

#define pb push_back

using namespace std;
ifstream in("alice2.in");
ofstream out("alice2.out");
const int N = 1e5 + 5;

int n, dist[N], lst[500];
char c[N];
vector<int> g[N];
queue<int> que;

int main()
{
    in >> c;
    n = strlen(c);

    for(int i=0; i<=500; i++)
        lst[i] = -1;

    for(int i=0; i<n; i++) {
        if(i > 0)
            g[i].pb(i-1);
        if(i < n - 1)
            g[i].pb(i+1);
        if(lst[c[i]] != -1) {
            g[lst[c[i]]].pb(i);
            g[i].pb(lst[c[i]]);
        }
        lst[c[i]] = i;
    }

    dist[0] = 1;
    que.push(0);
    while(!que.empty() && !dist[n-1]) {
        int nod = que.front();
        que.pop();

        for(auto nxt : g[nod])
            if(!dist[nxt]) {
                dist[nxt] = dist[nod] + 1;
                que.push(nxt);
            }
    }

    out << dist[n-1] - 1;
    return 0;
}
*/





/*
//Autobuze
#include <cstdio>
#include <algorithm>
#include <unordered_map>

using namespace std;

#define FILEIN "autobuze.in"
#define FILEOUT "autobuze.out"
#define NMAX 50005

unordered_map<int, int> Map(131071);
int n, v[NMAX];
int Sol[NMAX];
int Set[NMAX];
int Rank[NMAX];
bool Uz[NMAX];

inline int max(int a, int b) { return a > b ? a : b; }

int Find(int a) {
    int root = a;
    while (Set[root] != root)
        root = Set[root];

    while (Set[a] != a) {
        int tmp = Set[a];
        Set[a] = root;
        a = tmp;
    }

    return root;
}

void Union(int a, int b) {
    int rootA = Find(a);
    int rootB = Find(b);
    if (rootA == rootB)
        return;

    if (Rank[rootA] < Rank[rootB]) {
        Set[rootA] = rootB;
    } else if (Rank[rootA] > Rank[rootB]) {
        Set[rootB] = rootA;
    } else {
        Set[rootB] = rootA;
        Rank[rootA]++;
    }
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    scanf("%d", &n);
    int Max = 0;
    for ( int i = 1; i <= n; i++ ) {
        scanf("%d", &v[i]);
        Set[i] = i;
        Max = max(v[i], Max);
    }

    sort(v+1, v+n+1);
    for ( int i = 1; i <= n; i++ )
        Map[v[i]] = i;

    unordered_map<int, int>::iterator MapEnd = Map.end();

    for ( int i = 1; i <= n; i++ ) {
        if (!Uz[i]) {
            if (Max / v[i] < n) {
                for ( int val = 2*v[i]; val <= Max; val += v[i] ) {
                    unordered_map<int, int>::iterator iter = Map.find(val);
                    if (iter != MapEnd) {
                        int idx = iter->second;
                        Union(idx, i);
                        Uz[idx] = true;
                    }
                }
            } else {
                int minmultiple = 2 * v[i];
                int minidx = upper_bound(v+i, v+n+1, minmultiple) - v - 1;
                for ( int j = minidx; j <= n; j++ ) {
                    if (v[j] % v[i] == 0) {
                        Union(j, i);
                        Uz[j] = true;
                    }
                }
            }
        }
    }

    for ( int i = 1; i <= n; i++ ) {
        Sol[Find(i)]++;
    }

    int sol = 0;
    for ( int i = 1; i <= n; i++ ) {
        if (Sol[i])
            sol++;
    }
    printf("%d\n", sol);

    return 0;
}
*/









/*
//Freakadebunic
#include <bits/stdc++.h>
using namespace std;
ifstream fin("freakadebunic.in");
ofstream fout("freakadebunic.out");
const int NMAX = 1e5;

int parent[NMAX + 1];
int trupe[NMAX + 1];
bool devreme[NMAX + 1], viz[NMAX + 1];
int main() {
    int n, k;
    fin >> n >> k;
    for(int i = 0; i < k; i++)
        fin >> trupe[i];
    for(int i = 0; i < n - 1; i++) {
        int a, b;
        fin >> a >> b;
        if(a > b)
            parent[a] = b;
        else
            parent[b] = a;
    }
    for(int i = 0; i < k; i++) {
        int node = trupe[i];
        while(node != 1 && ! viz[node]) {
            viz[node] = true;
            node = parent[node];
        }
        devreme[node] = true;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans += devreme[i];
    fout << ans << endl;
    for(int i = 1; i <= n; i++)
        if(devreme[i])
            fout << i << ' ';
    fin.close();
    fout.close();
    return 0;
}
*/